Cod sursa(job #1456042)

Utilizator crysstyanIacob Paul Cristian crysstyan Data 29 iunie 2015 18:27:37
Problema Sate Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <fstream>
#include <vector>
#include <queue>
#define NMAX 30001

using namespace std;

ifstream f("sate.in");
ofstream g("sate.out");

int i, n, m, X, Y, x, y, dist, way[NMAX];

vector< pair < int, int> > v[NMAX];
queue <int> q;

int main()
{
    f>>n>>m>>X>>Y;

    for (i=1; i<=m; ++i)
    {
        f>>x>>y>>dist;
        v[x].push_back(make_pair(y,dist));
        v[y].push_back(make_pair(x,-dist));
    }
    q.push(X);
    for (int i=1; i<=n; ++i)
        way[i] = -1;
    way[X] = 0;

    while (!q.empty())
    {
        int a = q.front();
        q.pop();

        int nn = v[a].size();
        for (vector < pair <int, int> > :: iterator it = v[a].begin(); it != v[a].end(); ++it)
            if (way[it -> first] == -1)
        {
            way[it -> first] = way[a] + it -> second;
            q.push(it -> first);
        }
    }

    g<<way[Y]<<'\n';
    return 0;
}