Cod sursa(job #727239)

Utilizator lily3Moldovan Liliana lily3 Data 27 martie 2012 20:10:01
Problema Sate Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include<fstream>
#include<vector>
#include<queue>
using namespace std;

int i,j,n,m,x,y,xx,yy,cost1,d[300010],viz[3000010];
struct drum
{
	int nod,cost;
};
vector<drum> a[300010];
void bf(int x)
{
	int i;
	queue<int> q;
	q.push(x);
	for(i=1;i<=n;++i)
		d[i]=1<<30;
	d[x]=0;
	viz[x]=1;
	while(!q.empty())
	{
		x=q.front();
		for(i=0;i<a[x].size();++i)
			if(!viz[a[x][i].nod])
			{
				d[a[x][i].nod]=d[x]+a[x][i].cost,q.push(a[x][i].nod);
				viz[a[x][i].nod]=1;
			}
			q.pop();
	}
}
int main()
{
	FILE *f=fopen("sate.in","r");
	FILE *g=fopen("sate.out","w");
	fscanf(f,"%d%d%d%d",&n,&m,&x,&y);
	for(i=1;i<=m;++i)
	{
		fscanf(f,"%d%d%d",&xx,&yy,&cost1);
		a[xx].push_back((drum) {yy,cost1});
		a[yy].push_back((drum) {xx,-cost1});
	}
	bf(1);
	fprintf(g,"%d",d[y]-d[x]);
	return 0;
}