Pagini recente » Cod sursa (job #1727475) | Cod sursa (job #148569) | Cod sursa (job #2445261) | Cod sursa (job #2544745) | Cod sursa (job #282469)
Cod sursa(job #282469)
#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;
}