Cod sursa(job #182775)

Utilizator tm_raduToma Radu tm_radu Data 21 aprilie 2008 12:36:32
Problema Sate Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 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] )
        {
            if ( (nod <= x && x <= q->vf) || (q->vf <= x && x <= nod) ) d[q->vf] = q->c - d[nod];
            if ( (x <= nod && nod <= q->vf) || (q->vf <= nod && nod <= x) ) d[q->vf] = q->c + d[nod];
            if ( (nod <= q->vf && q->vf <= x) || (x <= q->vf && q->vf <= nod) ) d[q->vf] = 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;
}