Pagini recente » Cod sursa (job #275393) | Cod sursa (job #1753970) | Cod sursa (job #2907700) | Cod sursa (job #1756728) | Cod sursa (job #282474)
Cod sursa(job #282474)
#include<stdio.h>
#define N 30002
int n,m,x,y;
int *a[N],*b[N],deg[N]={0},v[N];
struct muchie{
int x,y,z;
}w[N];
void citire(){
int i;
scanf("%d%d%d%d",&n,&m,&x,&y);
for(i=1;i<=m;++i){
scanf("%d%d%d",&w[i].x,&w[i].y,&w[i].z);
deg[w[i].x]++;
deg[w[i].y]++;
}
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;
}
for(i=1;i<=m;++i){
a[w[i].x][++a[w[i].x][0]]=w[i].y;
a[w[i].y][++a[w[i].y][0]]=w[i].x;
b[w[i].x][++b[w[i].x][0]]=w[i].z;
b[w[i].y][++b[w[i].y][0]]=-w[i].z;
}
}
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]]=true;
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();
bfs();
return 0;
}