Shortest Routes I

#include <iostream>
#include <vector>
#include <cstdint>
#include <algorithm>
#include <queue>

int main() {
    int n, m;
    std::cin >> n >> m;

    using Edge = std::pair<uint64_t, int>;
    std::vector<std::vector<Edge>> flights(n);
    for (int i = 0; i < m; ++i) {
        int a, b;
        uint64_t c;
        std::cin >> a >> b >> c;
        flights[a-1].push_back({c, b-1});
    }

    std::vector<uint64_t> shortest(n, UINT64_MAX);
    shortest[0] = 0;
    std::vector<bool> processed(n, false);
    std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> elements_to_process;
    elements_to_process.push({0, 0});
    
    while (!elements_to_process.empty()) {
        int city = elements_to_process.top().second;
        elements_to_process.pop();
        if (processed[city]) continue;
        for (auto &flight : flights[city]) {
            if (shortest[city] + flight.first < shortest[flight.second]) {
                shortest[flight.second] = shortest[city] + flight.first;
                elements_to_process.push({shortest[flight.second], flight.second});
            }
        }
        processed[city] = true;
    }

    for (auto dist : shortest) {
        std::cout << dist << " ";
    }
}

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