Pagini recente » Cod sursa (job #759620) | Cod sursa (job #332469) | Cod sursa (job #1230555) | Cod sursa (job #2255455) | Cod sursa (job #68050)
Cod sursa(job #68050)
// sate O(M + N)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define NMax 30005
typedef struct lista { int idd, cost; struct lista *next; } lista;
int N, M, X, Y, S[NMax], q[NMax];
lista *G[NMax];
int modul(int X)
{ if (X < 0) return -X; return X; }
void add_to_list(lista **l, int item, int cst)
{
lista *tmp = (lista *)malloc(sizeof(lista));
tmp->idd = item;
tmp->cost = cst;
tmp->next = *l;
*l = tmp;
}
int main(void)
{
int i, u, v, D, ql, qr;
lista *f;
freopen("sate.in", "r", stdin);
freopen("sate.out", "w", stdout);
scanf("%d %d %d %d", &N, &M, &X, &Y);
for (i = 1; i <= M; i++)
{
scanf("%d %d %d", &u, &v, &D);
add_to_list(&G[u], v, D);
add_to_list(&G[v], u, D);
}
memset(S, -1, sizeof(S));
for (q[ql=qr=0]=X, S[X] = 0; qr <= ql; qr++)
for (f = G[q[qr]]; f; f = f->next)
if (S[f->idd] == -1)
{
q[++ql] = f->idd;
if ((f->idd - q[qr]) * (f->idd - X) < 0 ||
(X - q[qr]) * (X - f->idd) < 0)
S[f->idd] = modul(S[q[qr]] - f->cost);
else
S[f->idd] = S[q[qr]] + f->cost;
}
if (S[Y] == -1)
printf("NO\n");
else
printf("%d\n", S[Y]);
return 0;
}