Cod sursa(job #778264)

Utilizator gicu_01porcescu gicu gicu_01 Data 14 august 2012 13:13:11
Problema Sate Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <iostream>
#include <stdio.h>

using namespace std;

int v[4][200050];
int a[30010];
int n,m,start,end;

void dijkstra()
{
    int i,t;
    for (i=1; i<=n; ++i) a[i]=-1;
    a[1]=0; t=1;
    while (t)
    {
        t=0;
        for (i=1; i<=m*2; i++)
        {
            if ( a[v[1][i]]!=-1 && a[v[2][i]]==-1 && v[1][i]<v[2][i])
            {
                a[v[2][i]]=a[v[1][i]]+v[3][i];
                t=1;
            } else
            if ( a[v[1][i]]!=-1 && a[v[2][i]]==-1 && v[1][i]>v[2][i])
            {
                a[v[2][i]]=a[v[1][i]]-v[3][i];
                t=1;
            }
            //if (a[end]!=-1  && a[start!=-1]) {t=0; break;}
        }
    }
}

int main()
{
    int i;
    freopen("sate.in","r",stdin);
    freopen("sate.out","w",stdout);
    scanf("%i%i%i%i",&n,&m,&start,&end);
    for (i=1; i<=m*2; i++)
        if (i%2==1) scanf("%i%i%i",&v[1][i],&v[2][i],&v[3][i]); else
        {
            v[1][i]=v[2][i-1];
            v[2][i]=v[1][i-1];
            v[3][i]=v[3][i-1];
        }
    dijkstra();
    printf("%i",a[end]-a[start]);
    return 0;
}