Cod sursa(job #1369227)

Utilizator retrogradLucian Bicsi retrograd Data 2 martie 2015 22:45:16
Problema Algoritmul lui Dijkstra Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include<fstream>
#include<vector>
#include<queue>

using namespace std;
typedef int var;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

#define MAXN 100003
#define mp make_pair
#define INF (1<<28)

typedef pair<var, var> pii;

struct Edge {
    var n, c;
    Edge(var a, var b) {
    n = a; c = b;}
};
vector<Edge> G[MAXN];
var DIST[MAXN];
bool VIZ[MAXN];
var n;

struct cmp{
    const bool operator()(const pii &a, const pii &b) const{
    return a.second > b.second;
    }
};

priority_queue<pii, vector<pii>, cmp> Q;

void dijkstra(var start) {
    for(var i=1; i<=n; i++) {
        DIST[i] = INF;
        VIZ[i] = 0;
    }
    DIST[start] = 0;
    Q.push(mp(start, 0));
    while(!Q.empty()) {
        var node = Q.top().first;
        Q.pop();

        if(VIZ[node]) continue;
        else VIZ[node] = 1;

        for(auto e : G[node]) {
            if(DIST[e.n] > DIST[node] + e.c) {
                DIST[e.n] = DIST[node] + e.c;
                Q.push(mp(e.n, DIST[e.n]));
            }
        }
    }
}


int main() {
    var a, b, c, m;
    fin>>n>>m;
    while(m--) {
        fin>>a>>b>>c;
        G[a].push_back(Edge(b, c));
    }
    dijkstra(1);
    for(var i=2; i<=n; i++) {
        if(DIST[i] < INF)
            fout<<DIST[i]<<" ";
        else
            fout<<"0 ";
    }
}