Cod sursa(job #1129509)

Utilizator hellol30FMI Macovei Daniel hellol30 Data 27 februarie 2014 22:47:10
Problema Sate Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include<cstdio>
#include<queue>
#include<vector>
#define Nmax 30003
using namespace std;
int n,m,x,y,xt,yt,z;
vector< pair<int,int> > L[Nmax];

bool viz[Nmax];
int bfs(int x, int y)
{
	int distanta=0;
	int aux;
	queue<int> q;
	q.push(x); viz[x]=true;
	while(!q.empty())
	{
		aux=q.front(); q.pop();
		for(vector< pair<int,int> >::iterator it=L[aux].begin(); it!=L[aux].end(); it++)
			if(!viz[(*it).first])
			{
				viz[(*it).first]=true;
				if( aux > (*it).first ) distanta-=(*it).second;
				else distanta+=(*it).second;
				if( (*it).first == y ) return distanta;
				else
					q.push((*it).first);
			}
	}
	return -1;
}
int main()
{
	freopen("sate.in","rt",stdin);
	freopen("sate.out","wt",stdout);
	scanf("%d%d%d%d",&n,&m,&xt,&yt);
	for(int i=0;i<m;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		L[x].push_back(make_pair(y,z));
		L[y].push_back(make_pair(x,z));
	}
	printf("%d\n",bfs(xt,yt));
	return 0;
}