Cod sursa(job #182779)

Utilizator tm_raduToma Radu tm_radu Data 21 aprilie 2008 12:37:50
Problema Sate Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <stdio.h>
#define NM 30001

int n, m;
int i, j, k, d[NM], c[NM];
int s[NM], p, u, x, y;
typedef struct nod {
    int vf, c;
    nod* urm;
} NOD, *PNOD;
PNOD l[NM];

void Add(int i, int j, int k);
void DF(int nod);

int main()
{
    freopen("sate.in", "r", stdin);
    freopen("sate.out", "w", stdout);
    scanf("%d %d %d %d", &n, &m, &x, &y);
    if ( x > y ) x = x+y, y = x-y, x = x-y;
    for ( k = 1; k <= m; k++ )
        scanf("%d %d %d", &i, &j, &u),
        Add(i, j, u), Add(j, i, u);
    
    DF(x);
    
    printf("%d\n", d[y]);
    
    return 0;
}

void DF(int nod)
{
    if ( s[nod] ) return;
    s[nod] = 1;
    for ( PNOD q = l[nod]; q; q = q->urm )
        if ( !s[q->vf] )
        {
            int i = q->vf;
            if ( (nod <= x && x <= i) || (i <= x && x <= nod) ) d[i] = q->c - d[nod];
            if ( (x <= nod && nod <= i) || (i <= nod && nod <= x) ) d[i] = q->c + d[nod];
            if ( (nod <= i && i <= x) || (x <= i && i <= nod) ) d[i] = d[nod] - q->c;
            DF(q->vf);
        }
}

void Add(int i, int j, int k)
{
    PNOD q = new NOD;
    q->vf = j;
    q->c = k;
    q->urm = l[i];
    l[i] = q;
}