Shortest Routes I

#include <bits/stdc++.h>

using namespace std;

long long *dijkstra(int x, int n, vector<vector<pair<int, int>>> &adj) {
    // no negative weight
    // adj pairs are (node, weight)

    long long *distance = new long long[n];
    for (int i = 0; i < n; i++)
        distance[i] = LONG_LONG_MAX;
    
    priority_queue<pair<long long, int>> q;

    bool *processed = new bool[n];
    for (int i = 0; i < n; i++)
        processed[i] = false;

    distance[x] = 0;
    q.push({0, x});

    while (!q.empty()) {

        int a = q.top().second;
        q.pop();
        
        if (processed[a])
            continue;

        processed[a] = true;

        for (auto u : adj[a]) {
            int b = u.first, w = u.second;
            if (distance[a] + w < distance[b]) {
                distance[b] = distance[a] + w;
                q.push({-distance[b], b});
            }
        }

    }

    return distance;

}

int main() {

    int n, m;
    cin >> n >> m;

    vector<vector<pair<int, int>>> adj(n);

    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        a--, b--;
        adj[a].push_back({b, c});
    }

    long long *distance = dijkstra(0, n, adj);

    for (int i = 0; i < n; i++)
        cout << distance[i] << " ";
    cout << endl;

}

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