CSES – Shortest Routes I

#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define f first
#define s second
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
using namespace std;
//declare
const int maxn = 1e5+5;
int n,m,dis[maxn];
bool vis[maxn];
vector<pii> G[maxn];
//
void dijkstra(int start){
    priority_queue<pii,vector<pii>,greater<pii>> pq;
    pq.push({0,start});
    while(!pq.empty()){
        auto [weight,cur] = pq.top(); pq.pop();
        if(dis[cur] != 1e18) continue;
        dis[cur] = weight;
        for(auto [adj,w] : G[cur]){
            if(dis[cur] + w < dis[adj]){
                pq.push({dis[cur] + w,adj});
            }
        }
    }
}
signed main(){
    fastio;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b,c; cin>>a>>b>>c;
        G[a].push_back({b,c});
    }
    for(int i=1;i<=n;i++) dis[i] = 1e18;
    dijkstra(1);
    for(int i=1;i<=n;i++) cout<<dis[i]<<" ";
    cout<<"\n";
    return 0;
}