Cod sursa(job #2576322)

Utilizator MihneaGhiraMihnea MihneaGhira Data 6 martie 2020 18:33:53
Problema Algoritmul lui Dijkstra Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include<fstream>
#include<set>
#include<vector>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int n,m,x,y,c;
int D[50010];
vector < pair<int,int> > L[50010];
multiset < pair<int,int> > s;
int main(){
    fin>>n>>m;
    for(int i=1;i<=m;i++){
        fin>>x>>y>>c;
        L[x].push_back(make_pair(y,c));
    }
    for(int i=2;i<=n;i++){
        D[i]=1000000000;
    }
    s.insert(make_pair(0,1));
    while(!s.empty()){
        int nod=s.begin()->second;
        s.erase(s.begin());
        for(int i=0;i<L[nod].size();i++){
            int vecin=L[nod][i].first;
            int cost=L[nod][i].second;
            if(D[vecin]>D[nod]+cost){
                s.erase({D[vecin],vecin});
                D[vecin]=D[nod]+cost;
                s.insert({D[vecin],vecin});
            }
        }
    }
    for(int i=2;i<=n;i++){
        if(D[i]==1000000000)
            fout<<0<<" ";
        else
            fout<<D[i]<<" ";
    }
    return 0;
}