Cod sursa(job #2479138)

Utilizator radu_voroneanuVoroneanu Radu Stefan radu_voroneanu Data 23 octombrie 2019 12:45:25
Problema Algoritmul lui Dijkstra Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f

///#define fs first
///#define sc second
using namespace std;

typedef pair<int, pair<int,int>> piii;

vector<piii> G[200010], Sol;
priority_queue < piii, vector<piii>, greater<piii>> Q;
int N, M, x, y, c, k, cost, D[200010], T[200010]; bool sel[200010];

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

void load(){
    f >> N >> M;
    for( int i=1; i<=M; i++){
        f>>x>>y>>c;
        G[x].push_back({c,{x,y}});
    }
}

void dijkstra ( int p){

    for(int i = 1; i <= N; i++)
        D[i] = INF, T[i] = 0, sel[i] = false;
    sel[p] = true; D[p] = 0;
    for(auto i : G[p]){
        Q.push(i);
        D[i.second.second] = i.first;
    }

    while (!Q.empty()){
        while (!Q.empty() && sel[Q.top().second.second]) Q.pop();
        if (Q.empty()) break;
        k = Q.top().second.second;
        x = Q.top().second.first;
        c = Q.top().first;
        sel[k] = true;
        Q.pop();
        for(auto i: G[k])
           if(D[k] + i.first < D[i.second.second]){
                Q.push({D[k] + i.first, {k, i.second.second}});
                D[i.second.second] = D[k] + i.first;
                T[i.second.second] = k;
            }
    }
}

int main()
{
    load();
    dijkstra(1);
    for(int i = 2; i<=N; i++)
        g<<D[i]<<" ";
    return 0;
}