Cod sursa(job #870662)

Utilizator Sm3USmeu Rares Sm3U Data 3 februarie 2013 19:47:20
Problema Algoritmul lui Dijkstra Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include <cstdio>
#include <vector>
#include <queue>

#define nMax 50010
#define oo 912341231

using namespace std;

struct Nod{
    int catre;
    int lg;
    Nod (int x, int y){
        catre = x;
        lg = y;
    }
};

vector <Nod> graf[nMax];
int n;
int drum[nMax];
int nodViz[nMax];

struct cmp{
    bool operator () (const int &a, const int &b)const{
        return drum[a] > drum[b];
    }
};

priority_queue <int, vector <int>, cmp> q;

void citire(){
    int m;
    scanf ("%d %d", &n, &m);
    for (int i = 0; i < m; ++ i){
        int x;
        int y;
        int val;
        scanf ("%d %d %d", &x, &y, &val);
        graf[x].push_back (Nod(y, val));
    }
}

void dijkstra (int nod){
    for (int i = 1; i <= n; ++ i){
        drum[i] = oo;
    }
    nodViz [nod] = 1;
    drum[nod] = 0;
    q.push(nod);
    while (!q.empty()){
        nod = q.top();
        q.pop();
        for (int i = 0; i < graf[nod].size(); ++ i){
            if (drum[nod] + graf[nod][i].lg < drum[graf[nod][i].catre]){
                drum[graf[nod][i].catre] = drum[nod] + graf[nod][i].lg;
                q.push(graf[nod][i].catre);
            }
        }
    }
}

void afisare(){
    for (int i = 2; i <= n; ++i){
        if (drum[i] == oo){
            printf ("0 ");
            continue;
        }
        printf ("%d ", drum[i]);
    }
}

int main()
{
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);

    citire();
    dijkstra(1);
    afisare();

    return 0;
}