Cod sursa(job #1215940)

Utilizator rangerChihai Mihai ranger Data 2 august 2014 19:51:26
Problema Sate Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include<fstream>
#include<vector>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;

ifstream cin("sate.in");
ofstream cout("sate.out");

const int NMAX=30010;
vector < pair <int, int> > g[NMAX];
queue <int> q;
int n,m,x,y,i,D[NMAX],V[NMAX];

int main()
{
    cin>>n>>m>>x>>y;
    while (m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        if (a>b) swap(a,b);
        g[a].push_back(make_pair(b,c));
        g[b].push_back(make_pair(a,-c));
    }
    memset(D,-1,sizeof D);
    D[x]=0;
    q.push(x);
    V[x]=1;
    while (!q.empty())
    {
        int v=q.front();
        q.pop();
        for (i=0;i<g[v].size();i++)
        {
            int to=g[v][i].first;
            int d=g[v][i].second;
            if (!V[to])
            {
                V[to]=1;
                q.push(to);
                D[to]=D[v]+d;
            }
        }
    }
    cout<<D[y];
    return 0;

}