Cod sursa(job #282469)

Utilizator Matei14Popa-Matei Mihai Matei14 Data 17 martie 2009 18:07:25
Problema Sate Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include<stdio.h>
#define N 30002
int n,m,x,y;
int *a[N],*b[N],deg[N]={0},v[N];

void citire(){
	int i,x1,y1,d;
	scanf("%d%d%d%d",&n,&m,&x,&y);
	while(m--){
		scanf("%d%d%d",&x1,&y1,&d);
		deg[x1]++;
		deg[y1]++;
	}
	for(i=1;i<=n;++i){
		a[i]=new int[deg[i]+1];
		a[i][0]=0;
		b[i]=new int[deg[i]+1];
		b[i][0]=0;
	}
	fclose(stdin);
}

void calc(){
	int x1,y1,d;
	freopen("sate.in","r",stdin);
	scanf("%d%d%d%d",&n,&m,&x,&y);
	while(m--){
		scanf("%d%d%d",&x1,&y1,&d);
		a[x1][++a[x1][0]]=y1;
		a[y1][++a[y1][0]]=x1;
		b[x1][++b[x1][0]]=d;
		b[y1][++b[y1][0]]=-d;
	}
}



void bfs(){
	int u=0,p=1,i,x1,coada[N];
	bool viz[N]={false};
	coada[++u]=x;
	while(u>=p){
		x1=coada[p++];
		for(i=1;i<=a[x1][0];++i)
			if(!viz[a[x1][i]]){
				coada[++u]=a[x1][i];
				viz[a[x1][i]]=1;
				v[a[x1][i]]=b[x1][i]+v[x1];
			}
	}
	printf("%d\n",v[y]);
}

int main(){
	freopen("sate.in","r",stdin);
	freopen("sate.out","w",stdout);
	citire();
	calc();
	bfs();
	return 0;
}