Cod sursa(job #1927141)

Utilizator mariusn01Marius Nicoli mariusn01 Data 14 martie 2017 22:39:36
Problema Sate Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <fstream>
#include <vector>

using namespace std;

vector <pair <int, int> > L[30010];

int n, m, x, y, p, u, i, a, b, e;
int c[30010], v[30010], d[30010];

ifstream fin ("sate.in");
ofstream fout("sate.out");

int main () {
    fin>>n>>m>>x>>y;
    for (i=1;i<=m;i++) {
        fin>>a>>b>>e;
        L[a].push_back(make_pair(b, e));
        L[b].push_back(make_pair(a, -e));
    }

    c[1] = x;
    v[x] = 1;

    p = u = 1;
    while (p<=u) {
        int nod = c[p];
        for (int j=0;j<L[nod].size();j++) {
            int vecin = L[nod][j].first;
            int dist = L[nod][j].second;
            if (v[vecin] == 0) {
                u++;
                c[u] = vecin;
                d[vecin] = d[nod] + dist;
                v[vecin] = 1;
                if (vecin == y) {
                    fout<<d[y] > 0 ? d[y] : -d[y];
                    return 0;
                }
            }
        }
        p++;
    }

}