Cod sursa(job #1456049)

Utilizator crysstyanIacob Paul Cristian crysstyan Data 29 iunie 2015 18:35:34
Problema Sate Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>

#define x first
#define y second
#define NMAX 30007

using namespace std;

int n, m, X, Y, a, b, c;
vector < pair < int, int > > v[NMAX];
queue < int > q;
int Viz[NMAX];

int main(){
    freopen("sate.in", "r", stdin);
    freopen("sate.out", "w", stdout);
    scanf("%d %d %d %d", &n, &m, &X, &Y);
    for(int i = 1; i <= m; ++i){
        scanf("%d %d %d", &a, &b, &c);
        v[a].push_back(make_pair(b, c));
        v[b].push_back(make_pair(a, -c));
    }
    memset(Viz, -1, sizeof(Viz));
    q.push(X);
    Viz[X] = 0;
    while(!q.empty()){
        int Nod = q.front();
        q.pop();
        for(int i = 0; i < v[Nod].size(); ++i)
            if(Viz[v[Nod][i].x] == -1){
                Viz[v[Nod][i].x] = Viz[Nod] + v[Nod][i].y;
                q.push(v[Nod][i].x);
            }
    }
    printf("%d", Viz[Y]);
    return 0;
}