Cod sursa(job #802294)

Utilizator ghegoiu1Ghegoiu Stefan ghegoiu1 Data 26 octombrie 2012 12:41:18
Problema Sate Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <fstream>
#include <algorithm>
#include <queue>
#include <vector>
#define pb push_back
#define mkp make_pair

using namespace std;
bool sel[100005];
int nv[100005],n,m,X,Y,i,x,y,d;
vector <pair <int, int> > a[100005];
queue <int> Q;
ifstream f("sate.in");
ofstream g("sate.out");
void bf(int x)
{
    vector <pair <int, int> > :: iterator it;
    int nod;
    pair <int, int> z;
    Q.push(x);
    sel[x]=true;
    nv[x]=0;
    while (!Q.empty()) {
        nod=Q.front();
        for (it=a[nod].begin();it!=a[nod].end();it++) {
            z=*it;
            if (!sel[z.first])
                {
                    Q.push(z.first);
                    nv[z.first]=nv[nod]+z.second;
                    sel[z.first]=true;
                }
        }
        Q.pop();
    }
}
int main()
{
    f>>n>>m>>X>>Y;
    for (i=1;i<=m;i++) {
        f>>x>>y>>d;
        a[x].pb(mkp(y,d));
        a[y].pb(mkp(x,-d));
    }
    bf(X);
    g<<nv[Y];
    return 0;
}