Pagini recente » Cod sursa (job #457860) | Monitorul de evaluare | Cod sursa (job #1714796) | Cod sursa (job #2760690) | Cod sursa (job #1129752)
#include <fstream>
#include <vector>
#include <queue>
#define IN "sate.in"
#define OUT "sate.out"
#define NMAX 30005
using namespace std;
ifstream in(IN);
ofstream out(OUT);
vector < pair <int, int> > G[NMAX];
queue <int> Q;
int n, X, Y, d[NMAX];
bool Use[NMAX];
inline int BFS()
{
int i, nod;
Q.push(X);
Use[X]=true;
while(!Q.empty())
{
nod=Q.front();
Q.pop();
for(i=0; i<G[nod].size(); ++i)
if(!Use[G[nod][i].first])
{
Use[G[nod][i].first]=true;
if(nod > G[nod][i].first)
d[G[nod][i].first] = d[nod] + G[nod][i].second;
else
d[G[nod][i].first] = d[nod] - G[nod][i].second;
if(G[nod][i].first == Y)
return -d[Y];
else Q.push(G[nod][i].first);
}
}
return -1;
}
int main()
{
int m, i, a, b, c;
in>>n>>m>>X>>Y;
while(m--)
{
in>>a>>b>>c;
G[a].push_back(make_pair(b, c));
G[b].push_back(make_pair(a, c));
}
out<<BFS()<<'\n';
in.close();
out.close();
return 0;
}