Cod sursa(job #3375612)

Utilizator tulabongIvan Luca-Cristian tulabong Data 12 noiembrie 2026 16:50:51
Problema Algoritmul lui Dijkstra Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <iostream>
#include <queue>
#include <fstream>
#include <bitset>
#include <vector>

using namespace std;

ifstream fin("dijkstra.in"); 
ofstream fout("dijkstra.out");

const int nrMax = 50010;

vector<pair<int, int>> adj[nrMax];
vector<int> dist;
priority_queue <pair<int, int>, vector<pair<int, int>>, greater<pair<int,int>>> pq;

void dijkstra(int startNod){
    dist[startNod]=0;
    pq.push({0, startNod});
    while (!pq.empty()){
        auto [cost, node] = pq.top();
        pq.pop();
        for(auto [vecin, ncost]:adj[node]){
            if (dist[vecin] > dist[node]+ncost){
                dist[vecin] = dist[node]+ncost;
                pq.push({dist[vecin], vecin});
            }
        }
    }
}

int main(){
    int n, m;
    fin>>n>>m;
    dist.assign(n+1, 1<<19);
    for(int i=0; i<m; i++){
        int x, y, c;
        fin>>x>>y>>c;
        adj[x].push_back({y,c});
    }
    dijkstra(1);
    for(int i=2; i<=n; i++){
        fout<<dist[i]<<' ';
    }
    return 0;
}