Cod sursa(job #1074414)

Utilizator vld7Campeanu Vlad vld7 Data 7 ianuarie 2014 17:29:41
Problema Sate Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
#include <fstream>
#include <vector>

using namespace std;

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

const int MAX_N = 30005;

int n, m, X, Y, ans;

bool used[MAX_N];
vector < pair <int, int> > L[MAX_N];

void read() {
	f >> n >> m >> X >> Y;
	while (m--) {
		int a, b, c;
		f >> a >> b >> c;
		L[a].push_back (make_pair (b, c));
		L[b].push_back (make_pair (a, -c));
	}
}

void dfs (int nod, int from, int cost) {
	used[nod] = 1;
	if (nod == Y)
		ans = cost;
	for (size_t i = 0; i < L[nod].size(); i++) {
		int next = L[nod][i].first;
		if (from != next && !used[next])
			dfs (next, nod, cost + L[nod][i].second);
	}
}

int main() {
	read();
	dfs (X, 0, 0);
	
	g << ans << '\n';
	
	return 0;
}