Cod sursa(job #68050)

Utilizator filipbFilip Cristian Buruiana filipb Data 26 iunie 2007 12:37:43
Problema Sate Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.4 kb
// 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;
}