Cod sursa(job #482665)

Utilizator c_adelinaCristescu Adelina c_adelina Data 4 septembrie 2010 14:10:15
Problema Sate Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#include <cstdio>
#include <vector>
#include <cstring>
#define N 30003
#define pb push_back
using namespace std;

vector <int> v[N],cost[N];
int n,x,y,sol[N],s=1;

void rez(int k)
{
	sol[k]=s;
	vector<int> :: iterator it;
	while ((!v[k].empty()) && (!sol[y]))
	{
		int p=v[k].back(),cos=cost[k].back();
		v[k].pop_back();cost[k].pop_back();
		if (p<k) cos=-cos;
		if (!sol[p]) s+=cos,rez(p),s-=cos;
	}
}

int main()
{
	int m,i,a,b,c;
	
	freopen("sate.in","r",stdin);
	freopen("sate.out","w",stdout);
	scanf("%d %d %d %d",&n,&m,&x,&y);
	sol[x]=1;
	for (i=1;i<=m;++i)
	{scanf("%d %d %d",&a,&b,&c);v[a].pb(b);v[b].pb(a);
	 cost[a].pb(c);cost[b].pb(c);}
	rez(x);
	printf("%d",sol[y]-1);
	
return 0;}