Cod sursa(job #864631)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 25 ianuarie 2013 15:22:22
Problema Sate Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

typedef struct{

    int vecin;
    int cost;

} nod;

vector < vector <nod> > Graf;
vector <int> dist;
queue <int> Q;

int N, M;
int inceput, sfarsit;
int a, b, c;

void citire(){

    freopen("sate.in", "r", stdin);

    scanf("%d %d %d %d", &N, &M, &inceput, &sfarsit);

    Graf.resize(N+1);

    for(; M; M--){

        scanf("%d %d %d", &a, &b, &c);

        nod x = {b, c};
        nod y = {a, -c};

        Graf[a].push_back(x);
        Graf[b].push_back(y);
    }
}

void dijkstra(){

    dist.resize(N+1);
    Q.push(inceput);

    while(!Q.empty()){

        int current = Q.front();
        Q.pop();

        vector <nod> ::iterator it;

        for(it = Graf[current].begin(); it != Graf[current].end(); ++it){

            if(dist[it->vecin] == 0){

                dist[it->vecin] = dist[current] + it->cost;

                if(it->vecin == sfarsit)
                    return;

                Q.push(it->vecin);
            }
        }
    }
}

void afis(){

    freopen("sate.out", "w", stdout);

    printf("%lld\n", dist[sfarsit]);

}

int main(){

    citire();
    dijkstra();
    afis();

    return 0;
}