Cod sursa(job #1373991)

Utilizator sebinechitasebi nechita sebinechita Data 4 martie 2015 21:57:35
Problema Sate Scor 80
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 0.81 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("sate.in");
ofstream fout("sate.out");
#define MAX 30005

typedef vector <pair<int, int> > :: iterator iter;
vector<pair<int, int> > G[MAX];

int d[MAX], k, y1;

void df(int nod)
{
    if(d[y1])
        k = 1;
    for(iter it = G[nod].begin() ; !k && it != G[nod].end() ; it++)
    {
        if(!d[it->first])
        {
            d[it->first] = d[nod] + it->second;
            df(it->first);
        }
    }
}

int main()
{
    int n, m, x1, x, y, z;
    fin >> n >> m >> x1 >> y1;
    while(m--)
    {
        fin >> x >> y >> z;
        G[x].push_back(make_pair(y, z));
        G[y].push_back(make_pair(x, -z));
    }
    d[x1] = 20000005;
    df(x1);
    fout << d[y1] - d[x1] << "\n";
}