Pagini recente » Cod sursa (job #92787) | Cod sursa (job #1933146) | Cod sursa (job #2628812) | Cod sursa (job #1812474) | Cod sursa (job #842465)
Cod sursa(job #842465)
#include <stdio.h>
#include <algorithm>
#include <vector>
#define PAIR pair <int, int>
#define mp make_pair
#define x first
#define y second
using namespace std;
vector <PAIR> G[30100];
int sol = -1, target;
int dist[30100];
void DFS(int nod, int cost)
{
if (sol != -1)
return;
if (nod == target)
{
sol = cost;
return ;
}
vector <PAIR> :: iterator it;
dist[nod] = cost;
for (it = G[nod].begin(); it != G[nod].end(); it ++)
if (dist[it -> x] == 1 << 30)
DFS(it -> x, cost + it -> y);
}
int main()
{
int i, N, M, X, Y;
freopen("sate.in", "r", stdin);
freopen("sate.out", "w", stdout);
scanf("%d%d%d%d", &N, &M, &X, &target);
for (i = 1; i <= M; i ++)
{
int x0, y0, c;
scanf("%d%d%d", &x0, &y0, &c);
G[x0].push_back(mp(y0, c));
G[y0].push_back(mp(x0, -c));
}
for (i = 1; i <= N; i ++)
dist[i] = 1 << 30;
DFS(X, 0);
printf("%d", sol);
return 0;
}