Pagini recente » Cod sursa (job #1384404) | Cod sursa (job #1828199) | Cod sursa (job #1951962) | Cod sursa (job #244258) | Cod sursa (job #182775)
Cod sursa(job #182775)
#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;
}