Pagini recente » Cod sursa (job #2680833) | Cod sursa (job #1691524) | Cod sursa (job #2321137) | Cod sursa (job #868640) | Cod sursa (job #182779)
Cod sursa(job #182779)
#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;
}