Pagini recente » Cod sursa (job #1837587) | Cod sursa (job #1377409) | Cod sursa (job #2391389) | Cod sursa (job #2547531) | Cod sursa (job #1034076)
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
queue<int> q;
struct sat{
int x,d;
};
vector<sat> v[30001];
int e[30001];
void bfs(){
while ( !q.empty() ){
int x=q.front();
for ( int i=0;i<v[x].size();++i ){
if ( e[v[x][i].x]==-1 ){
if ( v[x][i].x>x ){
e[v[x][i].x]=e[x]+v[x][i].d;
q.push(v[x][i].x);
}
else {
e[v[x][i].x]=e[x]-v[x][i].d;
q.push(v[x][i].x);
}
}
}
q.pop();
}
}
int main()
{
FILE*f=fopen("sate.in","r");
FILE*h=fopen("sate.out","w");
int n,m,x,y;
fscanf(f,"%d%d%d%d",&n,&m,&x,&y);
for ( int i=1;i<=n;++i )
e[i]=-1;
q.push(x);
for ( int i=1;i<=m;++i ){
int a,b,d;
fscanf(f,"%d%d%d",&a,&b,&d);
sat w;
w.x=b;w.d=d;
v[a].push_back(w);
w.x=a;
v[b].push_back(w);
}
e[x]=0;
bfs();
fprintf(h,"%d",e[y]);
return 0;
}