Cod sursa(job #1385596)

Utilizator andreiblaj17Andrei Blaj andreiblaj17 Data 12 martie 2015 09:22:57
Problema Sate Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <iostream>
#include <fstream>
#include <vector>
#define nmax 30005
#define inf 20000005

using namespace std;

int n, m, x, y;
int dist[nmax];
vector < pair <int, int> > G[nmax];

void dfs(int nod) {
    if (dist[y])
        return;
    for (vector < pair<int, int> > :: iterator it = G[nod].begin(); it != G[nod].end(); ++it) {
        if (!dist[it -> first]) {
            dist[it -> first] = dist[nod] + it -> second;
            dfs(it -> first);
        }
    }
}

int main() {

    ifstream fin("sate.in");
    ofstream fout("sate.out");

    fin >> n >> m >> x >> y;
    for (int i = 1; i <= m; i++) {
        int a, b, c;
        fin >> a >> b >> c;
        G[a].push_back(make_pair(b, c));
        G[b].push_back(make_pair(a, -c));
    }

    dist[x] = 0;

    dfs(x);

    fout << dist[y] - dist[x] << "\n";

    fin.close();
    fout.close();

    return 0;
}