Cod sursa(job #68045)

Utilizator filipbFilip Cristian Buruiana filipb Data 26 iunie 2007 12:32:12
Problema Sate Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
// sate O(M + N)

#include <stdio.h>
#include <string.h>
#include <vector>

using namespace std;

#define NMax 30005
#define pb push_back
#define mp make_pair
#define f first
#define s second

int N, M, X, Y, S[NMax], q[NMax];
vector< pair<int, int> > G[NMax];

int modul(int X)
{ if (X < 0) return -X; return X; }

int main(void)
{
    int i, u, v, D, ql, qr;
    vector< pair<int, int> >::iterator it;
    
    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);
        G[u].pb( mp(v, D) );
        G[v].pb( mp(u, D) );
    }

    memset(S, -1, sizeof(S));
    
    for (q[ql=qr=0]=X, S[X] = 0; qr <= ql; qr++)
        for (it = G[q[qr]].begin(); it != G[q[qr]].end(); it++)
            if (S[it->f] == -1)
            {
                q[++ql] = it->f;
                if ((it->f - q[qr]) * (it->f - X) < 0 ||
                    (X - q[qr]) * (X - it->f) < 0)
                    S[it->f] = modul(S[q[qr]] - it->s);
                else
                    S[it->f] = S[q[qr]] + it->s;
                    
            }


    if (S[Y] == -1)
        printf("NO\n");
    else
        printf("%d\n", S[Y]);

    return 0;
}