Pagini recente » Cod sursa (job #1571968) | Cod sursa (job #369483)
Cod sursa(job #369483)
#include <stdio.h>
#include <vector>
#include <queue>
#define N 1<<15
#define mp make_pair
#define pb push_back
#define f first
#define s second
using namespace std;
int n,m,x,y;
int d[N];
char marc[N];
vector < pair <int, int> > v[N];
queue <int> Q;
void read()
{
scanf("%d%d%d%d",&n,&m,&x,&y);
int i,a,b,c;
for (i=1; i<=m; i++)
{
scanf("%d%d%d",&a,&b,&c);
v[a].pb(mp(b,c));
v[b].pb(mp(a,c));
}
}
void solve()
{
int i,t;
Q.push(x);
marc[x]=1;
while (!Q.empty())
{
t=Q.front();
Q.pop();
for (i=0; i<v[t].size(); i++)
if (!marc[v[t][i].f])
{
if (v[t][i].f<t)
d[v[t][i].f]=v[t][i].second+d[t];
else
d[v[t][i].f]=d[t]-v[t][i].second;
Q.push(v[t][i].f);
marc[v[t][i].f]=1;
}
}
}
int main()
{
freopen("sate.in","r",stdin);
freopen("sate.out","w",stdout);
read();
solve();
if (!marc[y])
printf("-1\n");
else
printf("%d\n",-d[y]);
return 0;
}