Cod sursa(job #1193884)

Utilizator varga13VarGaz13 varga13 Data 2 iunie 2014 09:44:42
Problema Sate Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <queue>
#define mx 30000
#define inf 2147483647
using namespace std;

int n,m,x,y;

vector< pair<int,int> > G[mx];
int best[mx];

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

void Initialisation()
{
    for(int i=0;i<mx;i++)
    {
        best[i]=0;
    }
}

void Read()
{
    f>>n>>m>>x>>y;
    Initialisation();
    for(int i=0;i<m;i++)
    {
        int a,b,d;
        f>>a>>b>>d;
        G[a].push_back( make_pair(b,d) );
        G[b].push_back( make_pair(a,-d) );
    }
}

void BFS(int curent)
{

    for(int i=0;i<G[curent].size();i++)
    {
        if(best[ G[curent][i].first ]==0)
        {
            best[G[curent][i].first]=best[curent]+G[curent][i].second;
            BFS(G[curent][i].first);
        }
    }
}

int main()
{
    Read();
    BFS(x);
    g<<best[y];
    return 0;
}

/*
int d, best[mx];
    queue<int> Q;

    for(Q.push(x) ; Q.size() ; Q.pop() )
    {
        for(int i=0;i<G[Q.back()].size();i++)//daca nu mere stim unde-i problema
        {
            int val;
            val=( Q.back()<G[Q.back()][i].first() ) ? G[Q.back()][i].second() : -G[Q.back()][i].second();
            best[G[Q.back()][i].first()]=
            Q.push(G[Q.back()][i].first());
        }

    }
*/