Cod sursa(job #296388)

Utilizator toni2007Pripoae Teodor Anton toni2007 Data 4 aprilie 2009 18:32:02
Problema Sate Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <cstdio>
#include <vector>
#include <bitset>

using namespace std;

#define pb 	push_back
#define maxN 	30010

int D[maxN], N, M, X, Y;
vector <int> A[maxN];
vector <int> C[maxN];
bitset <maxN> viz;

void df (int x) {
	viz[x] = 1;
	for (int i = 0; i < (int) A[x].size(); ++ i)
		if (!viz[A[x][i]]) {
			D[A[x][i]] = D[x] + C[x][i];
			df (A[x][i]);
		}
}

void parse () {
	char s[32];
	gets(s);

	int a = 0, b = 0, c = 0, i;

	for (i = 0; s[i] >= '0' && s[i] <= '9'; ++ i)
		a = (a << 1) + (a << 3) + s[i] - '0';

	for ( ++ i; s[i] >= '0' && s[i] <= '9'; ++ i)
		b = (b << 1) + (b << 3) + s[i] - '0';

	for ( ++ i; s[i] >= '0' && s[i] <= '9'; ++ i)
		c = (c << 1) + (c << 3) + s[i] - '0';

	A[a].pb(b);
	A[b].pb(a);
	C[a].pb(c);
	C[b].pb(-c);
}
int main () {

	freopen("sate.in", "r", stdin);
	freopen("sate.out", "w", stdout);

	scanf("%d%d%d%d\n", &N, &M, &X, &Y);

	for ( ; M -- ; ) {
		parse ();
	}

        df (X);
	printf("%d\n", D[Y]);
}