Pagini recente » Cod sursa (job #1351346) | Cod sursa (job #2073450) | Cod sursa (job #774592) | Cod sursa (job #2574348) | Cod sursa (job #1456045)
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#define NMAX 30002
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);
memset(way, -1, NMAX-1);
way[X] = 0;
while (!q.empty())
{
int a = q.front();
q.pop();
int nn = v[a].size();
for (vector < pair <int, int> > :: iterator it = v[a].begin(); it != v[a].end(); ++it)
if (way[it -> first] == -1)
{
way[it -> first] = way[a] + it -> second;
q.push(it -> first);
}
}
g<<way[Y]<<'\n';
return 0;
}