Shortest Routes I

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

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

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

    priority_queue<pair<int,int>,vector<pair<int,int>>, greater<>> pq;
    vector<int> dist(n+1, -1);
    dist[1]=0;
    pq.push({0, 1});
    while (!pq.empty()){
        auto p=pq.top();
        pq.pop();
        int 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 (int 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: WRONG ANSWER

Test 7

Verdict: WRONG ANSWER

Test 8

Verdict: WRONG ANSWER

Test 9

Verdict: WRONG ANSWER

Test 10

Verdict: WRONG ANSWER

Test 11

Verdict: ACCEPTED

Test 12

Verdict: WRONG ANSWER

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED