Pagini recente » oni_cl_11-12 | Cod sursa (job #403903) | Cod sursa (job #3174505) | Cod sursa (job #2828105) | Cod sursa (job #796727)
Cod sursa(job #796727)
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("sate.in");
ofstream fout("sate.out");
bool visited[30001];
vector<pair<int, int> >g[30001];
queue<int> q;
int c[30001], n, m, x, y, n1, n2, cost;
int Solve(int node, int destination)
{
int current = node;
q.push(current);
while ( !q.empty())
{
current = q.front();
for ( size_t i = 0; i < g[current].size(); i++ )
{
if ( c[current]+g[current][i].second < c[g[current][i].first] )
{
c[g[current][i].first]=c[current]+g[current][i].second;
q.push(g[current][i].first);
if ( g[current][i].first == destination )
{
return c[g[current][i].first];
}
}
}
q.pop();
}
}
int main()
{
fin >> n >> m >> x >> y;
for ( int i = 1; i <= n; i++ )
{
c[i] = 999999999;
fin >> n1 >> n2 >> cost;
g[n1].push_back(make_pair(n2,cost));
g[n2].push_back(make_pair(n1,-cost));
}
c[x] = 0;
fout << Solve(x,y);
return 0;
}