Cod sursa(job #1458056)

Utilizator blackoddAxinie Razvan blackodd Data 6 iulie 2015 13:13:29
Problema Sate Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

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

int n, m, x, y;
vector< vector < pair<int,int> > >G;
vector<int> d;
vector<bool>viz;
queue<int>Q;

int a, b, c;

int main()
{
    fin >> n >> m >> x >> y;

    G.resize(n + 1);
    d.resize(n + 1);
    viz.resize(n + 1);

    for ( int i = 0; i < m; ++i )
    {
        fin >> a >> b >> c;
        G[a].push_back({b,c});
        G[b].push_back({a,-c});
    }

    Q.push(x);
    viz[x] = true;
    d[x] = 0;

    while ( !Q.empty() )
    {
        int top = Q.front();
        Q.pop();

        for ( auto p : G[top] )
        {
            if ( !viz[p.first] ) {
                viz[p.first] = true;
                d[p.first] = d[top] + p.second;
                Q.push(p.first);
            }
        }
    }

    fout << d[y];

    fin.close();
    fout.close();
    return 0;
}