Pagini recente » Cod sursa (job #2570971) | Cod sursa (job #785803) | Cod sursa (job #2914548) | Cod sursa (job #521858) | Cod sursa (job #1456035)
#include <fstream>
#include <vector>
#include <queue>
#define NMAX 30001
using namespace std;
ifstream f("sate.in");
ofstream g("sate.out");
int i, n, m, X, Y, x, y, dist, way[NMAX];
vector< pair < int, int> > v[NMAX];
queue <int> q;
void read()
{
f>>n>>m>>X>>Y;
for (i=1; i<=m; ++i)
{
f>>x>>y>>dist;
v[x].push_back(make_pair(y,dist));
v[y].push_back(make_pair(x,-dist));
}
}
void initialize()
{
for (int i=1; i<=n; ++i)
way[i] = -1;
way[X] = 0;
}
void BFS()
{
q.push(X);
initialize();
while (!q.empty())
{
int a = q.front();
q.pop();
int nn = v[a].size();
for (i=0; i<nn; ++i)
if (way[v[a][i].first] == -1)
{
way[v[a][i].first] = way[a] + v[a][i].second;
q.push(v[a][i].first);
}
}
}
int main()
{
read();
BFS();
g<<way[Y]<<'\n';
return 0;
}