Cod sursa(job #2560277)

Utilizator mariusn01Marius Nicoli mariusn01 Data 27 februarie 2020 21:09:51
Problema Sate Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.97 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++;
    }
 
}