Mai intai trebuie sa te autentifici.

Cod sursa(job #3227785)

Utilizator philippePhilippe Colta philippe Data 2 mai 2024 16:40:27
Problema Algoritmul lui Dijkstra Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");
long long INF = 1e18;
priority_queue<pair<int, int> , vector<pair<int, int>> , greater<pair<int, int>> > Q;
vector<pair<int,int>>mat[50001];
int n, m;
long long dist[50001];
void djiksra(int start){
    for(int i = 1; i<=n; i++)dist[i] = INF;
    Q.push({0, start});
    while(!Q.empty()){
        int distance = Q.top().first;
        int nod = Q.top().second;
        Q.pop();
        if(distance > dist[nod])
            continue;
        for(auto vecin: mat[nod]){
            if(distance + vecin.second < dist[vecin.first] ){
                dist[vecin.first] = distance + 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});
    }

    djiksra(1);
    for(int i = 2; i<=n; i++){
        cout << dist[i] << ' ';
    }
    return 0;
}