Cod sursa(job #1801507)

Utilizator valentinoMoldovan Rares valentino Data 9 noiembrie 2016 09:09:45
Problema Sate Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <fstream>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#define NM 30005
using namespace std;

ifstream f("sate.in");
ofstream g("sate.out");
vector < pair < int, int > > v[NM];
queue < int > coada;
int n, m, x, y, cost[NM];

void Read()
{
    int nod1, nod2, d;
    f >> n >> m >> x >> y;
    for(int i = 1; i <= m; ++i)
    {
        f >> nod1 >> nod2 >> d;
        if(nod2 < nod1)
        {
            int aux = nod1;
            nod1 = nod2;
            nod2 = aux;
        }
        v[nod1].push_back(make_pair(nod2, d));
        v[nod2].push_back(make_pair(nod1, -d));
    }
}

void BFS(int nod)
{
    int nod2;
    for(int i = 1; i <= NM - 1; ++i)
        cost[i] = -1;
    coada.push(nod);
    cost[nod] = 0;
    while(!coada.empty())
    {
        nod2 = coada.front();
        //cout << nod2;
        coada.pop();
        for(int i = 0; i < v[nod2].size(); ++i)
        {
            if(cost[ v[ nod2 ][ i ].first ] == -1)
            {
                coada.push(v[ nod2 ][ i ].first);
                cost[ v[ nod2 ][ i ].first ] = cost[nod2] + v[ nod2 ][ i ].second;
            }

        }
    }

}

int main()
{
    Read();
    BFS(x);
    g << cost[y] << '\n';
}