Cod sursa(job #3375528)

Utilizator Mirc100Mircea Octavian Mirc100 Data 12 noiembrie 2026 11:01:59
Problema Algoritmul lui Dijkstra Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
using namespace std;

int main(){

    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");

    int n,m;
    f >> n >> m;

    vector<vector<pair<int, int>>> v(n + 1);

    for (int i = 0; i < m; i++) {
        int a, b, c;
        f >> a >> b >> c;
        v[a].push_back({b, c});
    }

    int s = 1;
    vector <int> dist(n + 1, INT_MAX);
    dist[s] = 0;


    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, s});


    while(pq.size() > 0){
        int dist_curenta = pq.top().first;
        int nod_curent = pq.top().second;
        pq.pop();

        if (dist_curenta > dist[nod_curent]) {
            continue;
        }

        for( auto muchie : v[nod_curent]){
            int vecin = muchie.first;
            int cost = muchie.second;

            if(dist_curenta + cost < dist[vecin]){
                dist[vecin] = dist_curenta + cost;
                pq.push({dist[vecin], vecin});
            }
        }

    }

    for(int i = 1; i <= n; i++){
        if(i == s) continue;
        if(dist[i] == INT_MAX)
            g << "0 ";
        else
            g << dist[i] << " ";
    }



    return 0;
}