Cod sursa(job #866662)

Utilizator razvan.popaPopa Razvan razvan.popa Data 28 ianuarie 2013 16:19:20
Problema Sate Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include<iostream>
#include<iostream>
#include<fstream>
#include<cstdio>
#include<cstring>
#include<iomanip>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<bitset>
#include<algorithm>
#define INF (1 << 30)
#define pb push_back
#define mkp make_pair
#define pii pair<int, int>
#define ll long long
#define nxt (*it).first
#define cst (*it).second
#define type pii
#define FORi(i,a,b)\
   for(int i=a; i<=b; ++i)
#define FORr(g)\
   for(vector<type>::reverse_iterator it=g.rbegin(); it!=g.rend(); ++it)
#define FOR(g)\
   for(vector<type>::iterator it=g.begin(); it!=g.end(); ++it)
#define infile "sate.in"
#define outfile "sate.out"
#define nMax 30005
using namespace std;

vector < type > v[nMax];

vector < int > Dist(nMax, -1);

int N, M, X, Y;

void read(){
    ifstream f(infile);

    f >> N >> M >> X >> Y;

    int x, y, cost;
    while(M--){
        f >> x >> y >> cost;
        v[x].pb(mkp(y,  cost));
        v[y].pb(mkp(x, -cost));
    }

    f.close();
}

void BFS(){
    queue < int > q;
    Dist[1] = 0;
    q.push(1);

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

        FOR(v[x])
           if(Dist[nxt] == -1){
               Dist[nxt] = Dist[x] + cst;
               q.push(nxt);
           }
    }
}

void print(){
    ofstream g(outfile);

    g << Dist[Y] - Dist[X] << '\n';

    g.close();
}

int main(){
    read();
    BFS();
    print();

    return 0;
}