Shortest Routes I

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main(){
    long long n, m;
    cin >> n >> m;
    vector<vector<pair<long long,long long>>> g(n+1,vector<pair<long long,long long>>(0));

    for (long long i=0;i<m;i++){
        long long from, to, cost;
        cin >> from >> to >> cost;
        g[from].push_back({to, cost});
    }

    priority_queue<pair<long long,long long>,vector<pair<long long,long long>>, greater<>> pq;
    vector<long long> dist(n+1, -1);
    dist[1]=0;
    pq.push({0, 1});
    while (!pq.empty()){
        auto p=pq.top();
        pq.pop();
        long long curr=p.second, cost=p.first;
        if (cost>dist[curr]){
            continue;
        }
        //cout << "Now on "<<curr<<", cost " <<cost <<"\n";
        for (const auto& next: g[curr]){
            if (dist[next.first]==-1 || dist[next.first]>cost+next.second){
                dist[next.first]=cost+next.second;
                pq.push({cost+next.second, next.first});
            }
        }
    }
    for (long long i=1;i<=n;i++){
        cout << dist[i] << ' ';
    }
    cout << '\n';
    return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED