Cod sursa(job #842465)

Utilizator elfusFlorin Chirica elfus Data 26 decembrie 2012 21:47:33
Problema Sate Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <stdio.h>
#include <algorithm>
#include <vector>

#define PAIR pair <int, int>
#define mp make_pair
#define x first
#define y second

using namespace std;

vector <PAIR> G[30100];

int sol = -1, target;
int dist[30100];

void DFS(int nod, int cost)
{
    if (sol != -1)
        return;
    if (nod == target)
    {
        sol = cost;
        return ;
    }

    vector <PAIR> :: iterator it;

    dist[nod] = cost;
    for (it = G[nod].begin(); it != G[nod].end(); it ++)
        if (dist[it -> x] == 1 << 30)
            DFS(it -> x, cost + it -> y);
}

int main()
{
    int i, N, M, X, Y;

    freopen("sate.in", "r", stdin);
    freopen("sate.out", "w", stdout);

    scanf("%d%d%d%d", &N, &M, &X, &target);
    for (i = 1; i <= M; i ++)
    {
        int x0, y0, c;

        scanf("%d%d%d", &x0, &y0, &c);
        G[x0].push_back(mp(y0, c));
        G[y0].push_back(mp(x0, -c));
    }

    for (i = 1; i <= N; i ++)
        dist[i] = 1 << 30;
    DFS(X, 0);

    printf("%d", sol);
    return 0;
}