Cod sursa(job #851535)

Utilizator crushackPopescu Silviu crushack Data 10 ianuarie 2013 00:56:11
Problema Sate Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.68 kb
#include <stdio.h>
#include <vector>
#define NMax 30010
using namespace std;

const char IN[]="sate.in",OUT[]="sate.out";

int N,M,X,Y;
int D[NMax];
bool b[NMax];
vector<pair<int,int> > v[NMax];

void dfs(int x)
{
	b[x]=true;
	for (int i=0;i<(int)v[x].size();++i) if (!b[v[x][i].first])
		D[v[x][i].first]=D[x]+v[x][i].second,
		dfs(v[x][i].first);
}

int main()
{
	int i,x,y,c;
	freopen(IN,"r",stdin);
	scanf("%d%d%d%d",&N,&M,&X,&Y);
	for (i=1;i<=M;++i)
		scanf("%d%d%d",&x,&y,&c),
		v[x].push_back(make_pair(y,c)),
		v[y].push_back(make_pair(x,-c));
	fclose(stdin);

	dfs(X);

	freopen(OUT,"w",stdout);
	printf("%d\n",D[Y]);
	fclose(stdout);

	return 0;
}