Pagini recente » Cod sursa (job #819691) | Cod sursa (job #2185834) | Cod sursa (job #2105511) | Cod sursa (job #3191215) | Cod sursa (job #778263)
Cod sursa(job #778263)
#include <iostream>
#include <stdio.h>
using namespace std;
int v[4][200050];
int a[30010];
int n,m,start,end;
void dijkstra()
{
int i,t;
for (i=1; i<=n; ++i) a[i]=-1;
a[1]=0; t=1;
while (t)
{
t=0;
for (i=1; i<=m*2; i++)
{
if ( a[v[1][i]]!=-1 && a[v[2][i]]==-1 && v[1][i]<v[2][i])
{
a[v[2][i]]=a[v[1][i]]+v[3][i];
t=1;
} else
if ( a[v[1][i]]!=-1 && a[v[2][i]]==-1 && v[1][i]>v[2][i])
{
a[v[2][i]]=a[v[1][i]]-v[3][i];
t=1;
}
//if (a[end]!=-1 && a[start!=-1]) {t=0; break;}
}
}
}
int main()
{
int i;
freopen("sate.in","r",stdin);
freopen("sate.out","w",stdout);
scanf("%i%i%i%i",&n,&m,&start,&end);
for (i=1; i<=m*2; i++)
if (i%2==1) scanf("%i%i%i",&v[1][i],&v[2][i],&v[3][i]); else
{
v[1][i]=v[2][i-1];
v[2][i]=v[1][i-1];
v[3][i]=v[3][i-1];
}
dijkstra();
printf("%i",a[end]-a[start]);
return 0;
}