Cod sursa(job #1374001)

Utilizator sebinechitasebi nechita sebinechita Data 4 martie 2015 22:02:46
Problema Sate Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 1.45 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);
        }
    }
}

const unsigned maxb = 8192;
char buf[maxb];
unsigned ptr = maxb - 1;

int getInt()
{
    int rez = 0;
    while(!(buf[ptr] >= '0' && buf[ptr] <= '9'))
    {
        if(++ptr >= maxb)
        {
            fin.read(buf, maxb);
            ptr = 0;
        }
    }
    while((buf[ptr] >= '0' && buf[ptr] <= '9'))
    {
        rez = rez * 10 + buf[ptr] - '0';
        if(++ptr >= maxb)
        {
            fin.read(buf, maxb);
            ptr = 0;
        }
    }
    return rez;
}

int main()
{
    int n, m, x1, x, y, z;
    n = getInt();
    m = getInt();
    x1 = getInt();
    y1 = getInt();
    //fin >> n >> m >> x1 >> y1;

    while(m--)
    {
        x = getInt();
        y = getInt();
        z = getInt();
        //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";
}