Pagini recente » Cod sursa (job #1630048) | Cod sursa (job #1973885) | Cod sursa (job #463044) | Cod sursa (job #1083016) | Cod sursa (job #1456036)
#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;
int main()
{
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));
}
q.push(X);
for (int i=1; i<=n; ++i)
way[i] = -1;
way[X] = 0;
while (!q.empty())
{
int a = q.front();
q.pop();
int nn = v[a].size();
for (i=0; i<v[a].size(); ++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);
}
}
g<<way[Y]<<'\n';
return 0;
}