Cod sursa(job #2748827)

Utilizator RobertAcAcatrinei Robert-Marian RobertAc Data 3 mai 2021 16:11:38
Problema Algoritmul lui Dijkstra Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <bits/stdc++.h>

using namespace std;
string prob="dijkstra";
ifstream in(prob+".in");
ofstream out(prob+".out");
vector< vector< pair<int,int> > > v(50001);
vector<int> dist(50001);
priority_queue<pair<int,int>> q;
void dij(){
    q.push({0,1});
    while(!q.empty()){
        pair<int,int> n=q.top();
        //cout<<n.first<<" "<<n.second<<"\n";
        q.pop();
        int ff=n.second;
        for(auto i:v[ff]){
            int f=i.first;
            int s=i.second;
            if(dist[f]==0&&f!=1){
                dist[f]=dist[ff]-s;
                q.push(make_pair(s,f));
            }
        }
    }
}
int main(){
    int n,m;
    in>>n>>m;
    for(;m;m--){
        int a,b,c;
        in>>a>>b>>c;
        v[a].push_back(make_pair(b,-c));
    }
    dij();
    for(int i=2;i<=n;i++)out<<dist[i]<<" ";

}