Pagini recente » Cod sursa (job #2660559) | Cod sursa (job #1499443) | Cod sursa (job #2375973) | Cod sursa (job #1646519) | Cod sursa (job #326559)
Cod sursa(job #326559)
#include<cstdio>
#include<vector>
using namespace std;
const int N=30001;
int n,m;
short int x0,y0;
int dd[N];
vector<int> d[N];
vector<short int> a[N];
void citire()
{
short int x,y;
int dist;
scanf("%d%d%hd%hd",&n,&m,&x0,&y0);
while(m--)
{
scanf("%hd%hd%d",&x,&y,&dist);
a[x].push_back(y);
a[y].push_back(x);
d[x].push_back(dist);
d[y].push_back(dist);
}
}
int bfs()
{
short int i,s,p=1,u=0,x,y,coada[N];
coada[++u]=x0;
dd[x0]=1;
while(p<=u)
{
x=coada[p++];
for(i=0,s=a[x].size() ; i<s ; ++i)
{
y=a[x][i];
if(dd[y]==0)
{
if(x<y)
dd[y]=dd[x]+d[x][i];
else
dd[y]=dd[x]-d[x][i];
coada[++u]=y;
if(y==y0)
return dd[y]-1;
}
}
}
return -1;
}
int main()
{
freopen("sate.in","r",stdin);
freopen("sate.out","w",stdout);
citire();
printf("%d\n",bfs());
return 0;
}