Pagini recente » Clasament qwerty5 | alinsava | Cod sursa (job #281685) | Rating Cont disperare tudose (AlternateTudose) | Cod sursa (job #1129519)
#include<cstdio>
#include<queue>
#include<vector>
#define Nmax 30003
using namespace std;
int n,m,x,y,xt,yt,z;
vector< pair<int,int> > L[Nmax];
int distanta[Nmax];
bool viz[Nmax];
int bfs(int x, int y)
{
int aux;
queue<int> q;
q.push(x); viz[x]=true;
while(!q.empty())
{
aux=q.front(); q.pop();
for(vector< pair<int,int> >::iterator it=L[aux].begin(); it!=L[aux].end(); it++)
if(!viz[(*it).first])
{
viz[(*it).first]=true;
if( aux > (*it).first ) distanta[(*it).first]=distanta[aux]-(*it).second;
else distanta[(*it).first]=distanta[aux]+(*it).second;
if( (*it).first == y ) return distanta[(*it).first];
else
q.push((*it).first);
}
}
return -1;
}
int main()
{
freopen("sate.in","rt",stdin);
freopen("sate.out","wt",stdout);
scanf("%d%d%d%d",&n,&m,&xt,&yt);
for(int i=0;i<m;i++)
{
scanf("%d%d%d",&x,&y,&z);
L[x].push_back(make_pair(y,z));
L[y].push_back(make_pair(x,z));
}
printf("%d\n",bfs(xt,yt));
return 0;
}