Cod sursa(job #3375691)

Utilizator Andreea345Vaduva Andreea Andreea345 Data 13 noiembrie 2026 08:30:17
Problema Algoritmul lui Dijkstra Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <bits/stdc++.h>
#include <queue>
using namespace std;
const int NMAX=5e4;
int n,m;
int vis[NMAX+1],d[NMAX+1];
vector<pair<int,int>>L[NMAX+1];
void dijh(int s){
    for(int i=1;i<=n;++i){
        d[i]=1e9;
    }
    d[s]=0;
    priority_queue<pair<int,int>>pq;
    pq.push({-d[s],s});
    while(pq.empty()==false){
        int nod=pq.top().second;
        pq.pop();
        if(vis[nod]) continue;
        vis[nod]=1;
        for(auto it:L[nod]){
            int vec=it.first;
            int cost=it.second;
            if(d[vec]>d[nod]+cost){
                d[vec]=d[nod]+cost;
                pq.push({-d[vec],vec});
            }
        }
    }
}
int main() {
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m;
    for(int i=1;i<=m;++i){
        int x,y,c;
        cin>>x>>y>>c;
        L[x].push_back({y,c});
    }
    dijh(1);
    for(int i=2;i<=n;++i){
        if(d[i]==1e9) cout<<0<<" ";
        else cout<<d[i]<<" ";
    }
    cout<<"\n";
}