Cod sursa(job #1169720)

Utilizator OlaruSabinOlaru Sabin OlaruSabin Data 11 aprilie 2014 22:02:49
Problema Sate Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include<cstdio>
#include<vector>
using namespace std;
vector<int>cost[100010],v[100010];
int costdrum,nod1,nod2,n,m,plecare,sosire,viz[50000],rasp[50000],i,coada[50000];
int bfs(int nod)
{
	int ic=1;
	int sf=1;
	coada[ic]=nod;
	while(ic<=sf)
	{
		for(i=0;i<=v[coada[ic]].size()-1;i++)
		{
			if(!viz[v[coada[ic]][i]])
			{
				if(v[coada[ic]][i]>coada[ic])
				   rasp[v[coada[ic]][i]]=rasp[coada[ic]]+cost[coada[ic]][i];
				else
					rasp[v[coada[ic]][i]]=rasp[coada[ic]]-cost[coada[ic]][i];
				coada[++sf]=v[coada[ic]][i];
				viz[v[coada[ic]][i]]=1;
				if(v[coada[ic]][i]==sosire)
					return 0;
			}
		}
		++ic;
	}
}
int main()
{
	freopen("sate.in","r",stdin);
	freopen("sate.out","w",stdout);
	scanf("%d%d%d%d",&n,&m,&plecare,&sosire);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&nod1,&nod2,&costdrum);
		v[nod1].push_back(nod2);
		v[nod2].push_back(nod1);
		cost[nod1].push_back(costdrum);
		cost[nod2].push_back(costdrum);
	}
	viz[plecare]=1;
	bfs(plecare);
	printf("%d",rasp[sosire]);
}