Cod sursa(job #3227855)

Utilizator philippePhilippe Colta philippe Data 3 mai 2024 10:57:34
Problema Algoritmul lui Dijkstra Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");
#define ll long long
#define pll pair<ll, ll>
long long INF = 1e18;
priority_queue<pll , vector<pll> , greater<pll>> Q;
vector<pll>mat[50001];
int n, m;
long long dist[50001];
void dijkstra(int start){
    for(int i = 2; i<=n; i++)dist[i] = INF;
    Q.push({0, start});
    while(!Q.empty()){
        ll distance = Q.top().first;
        ll nod = Q.top().second;
        Q.pop();
        if(distance > dist[nod])
            continue;
        for(auto vecin: mat[nod]){
            if(dist[nod] + vecin.second < dist[vecin.first] ){
                dist[vecin.first] = dist[nod] + vecin.second;
                Q.push({dist[vecin.first], vecin.first});
            }
        }
    }
}
int main() {
    cin >> n >> m;
    for(int i = 1; i<=m; i++){
        int x, y, c;
        cin >> x >> y >> c;
        mat[x].push_back({y, c});
    }

    dijkstra(1);
    for(int i = 2; i<=n; i++){
        if(dist[i] == INF)cout << 0 << ' ';
        else   cout << dist[i] << ' ';

    }
    return 0;
}