Cod sursa(job #1577046)

Utilizator TopiAlexTopala Alexandru TopiAlex Data 23 ianuarie 2016 10:46:37
Problema Sate Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#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];
    }
}