Pagini recente » Cod sursa (job #406931) | Cod sursa (job #693706) | Cod sursa (job #1073844) | Solutii preONI 2007, Runda 3 | Cod sursa (job #1577046)
#include <stdio.h>
#define N_MAX 30002
#define M_MAX 100026
using namespace std;
struct Pair {
int nod;
int cost;
};
int n, m;
int X, Y;
int lst[N_MAX];
Pair vf[M_MAX * 2];
int urm[M_MAX * 2];
bool viz[N_MAX];
int cost;
bool found = false;
inline void citire();
void BFS(int);
int main()
{
citire();
BFS(X);
if (cost < 0)
cost *= -1;
printf("%d\n", cost);
return 0;
}
inline void citire(){
freopen("sate.in", "r", stdin);
freopen("sate.out", "w", stdout);
scanf("%d%d%d%d", &n, &m, &X, &Y);
int counter = 0;
int x, y, c;
for (int i = 1; i <= m; ++i){
scanf("%d%d%d", &x, &y, &c);
counter++;
vf[counter].nod = y;
vf[counter].cost = c;
urm[counter] = lst[x];
lst[x] = counter;
counter++;
vf[counter].nod = x;
vf[counter].cost = c;
urm[counter] = lst[y];
lst[y] = counter;
}
}
void BFS(int nod){
viz[nod] = true;
int poz;
int y;
int c;
poz = lst[nod];
if (nod == Y)
found = true;
while (poz != 0 && !found){
y = vf[poz].nod;
c = vf[poz].cost;
if (!viz[y]){
if (nod < y) cost += c;
else cost -= c;
BFS(y);
}
poz = urm[poz];
}
}