Pagini recente » Cod sursa (job #1165254) | Cod sursa (job #220823) | Cod sursa (job #192855) | Cod sursa (job #226406) | Cod sursa (job #1801507)
#include <fstream>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#define NM 30005
using namespace std;
ifstream f("sate.in");
ofstream g("sate.out");
vector < pair < int, int > > v[NM];
queue < int > coada;
int n, m, x, y, cost[NM];
void Read()
{
int nod1, nod2, d;
f >> n >> m >> x >> y;
for(int i = 1; i <= m; ++i)
{
f >> nod1 >> nod2 >> d;
if(nod2 < nod1)
{
int aux = nod1;
nod1 = nod2;
nod2 = aux;
}
v[nod1].push_back(make_pair(nod2, d));
v[nod2].push_back(make_pair(nod1, -d));
}
}
void BFS(int nod)
{
int nod2;
for(int i = 1; i <= NM - 1; ++i)
cost[i] = -1;
coada.push(nod);
cost[nod] = 0;
while(!coada.empty())
{
nod2 = coada.front();
//cout << nod2;
coada.pop();
for(int i = 0; i < v[nod2].size(); ++i)
{
if(cost[ v[ nod2 ][ i ].first ] == -1)
{
coada.push(v[ nod2 ][ i ].first);
cost[ v[ nod2 ][ i ].first ] = cost[nod2] + v[ nod2 ][ i ].second;
}
}
}
}
int main()
{
Read();
BFS(x);
g << cost[y] << '\n';
}