Cod sursa(job #3375545)

Utilizator cristiana_6Dode Cristiana cristiana_6 Data 12 noiembrie 2026 11:17:40
Problema Algoritmul lui Dijkstra Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
using namespace std;

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

const int MAX=20001;

vector<int> tata;
vector<int> dist;
vector<vector<pair<int, int>>> v;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;


void dijkstra(int src){
    dist[src] = 0;
    pq.push({0, src});

    while(!pq.empty()){
        int d = pq.top().first;
        int n = pq.top().second;
        pq.pop();

        if(d > dist[n]){
            continue;
        }

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

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

int main(){
    int x, y, p, n, m;
    fin>>n>>m;

    dist.assign(n+1, MAX);
    tata.assign(n+1, 0);

    v.resize(n+1);
    for(int i=0; i<m; i++){
        fin>>x>>y>>p;
        v[x].push_back({y, p});
    }

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

    return 0;
}