Cod sursa(job #2532093)

Utilizator Seb0730Matei Sebastian Seb0730 Data 27 ianuarie 2020 12:44:16
Problema Algoritmul lui Dijkstra Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
int n, m, a, b, c, x, y, dist[100000];


struct abc{
    int nod, cost;
    bool operator <(const abc&a) const{
        return cost>a.cost;
    }
};


vector<abc> v[100000];
priority_queue <abc> q;



int main()
{
    in>>n>>m;
    for(int i=1;i<=n;i++)dist[i]=1<<30;
    for(int i=1;i<=m;i++){
        in>>a>>b>>c;
        v[a].push_back({b, c});
        v[b].push_back({a, c});

    }
    q.push({1, 0});
    dist[1]=0;
    while(!q.empty()){
        x=q.top().nod;
        y=q.top().cost;
        q.pop();
        if(y!=dist[x])continue;
        for(auto i:v[x]){
            if(dist[i.nod]>dist[x]+i.cost){
                dist[i.nod]=dist[x]+i.cost;
                q.push({i.nod, dist[i.nod]});
            }

        }
    }
    for(int i=2;i<=n;i++){
        if(dist[i]==1<<30)dist[i]=0;
        out<<dist[i]<<" ";
    }
}