Shortest Routes I

#include <iostream>
#include <vector>
#include <cmath>
#include <bits/stdc++.h>

using namespace std;

void dijkstra(vector<vector<pair<long long, long long>>> graph, vector<long long> & distance, vector<bool> & visited)
{
    priority_queue<pair<long long, long long>> to_visit;
    to_visit.push({0,1}); // 0 for weight, 1 for starting point
    while (!to_visit.empty())
    {
        int a = to_visit.top().second; to_visit.pop();
        if (visited[a]) continue;
        visited[a] = true;
        for (auto u : graph[a])
        {
            int b = u.first, w = u.second;
            if (distance[a]+w < distance[b])
            {
                distance[b] = distance[a]+w;
                to_visit.push({-distance[b],b});
            }
        }
    }
}



int main()
{
    long long n_cities;
    long long flights;
    cin >> n_cities >> flights;


    vector<bool> visited(n_cities + 1, false);
    vector<long long> distance(n_cities + 1, LONG_LONG_MAX);
    distance[1] = 0;
    vector<vector<pair<long long, long long>>> graph(n_cities + 1);
    for(int i = 0; i < flights; ++i)
    {
        int a, b, c;
        cin >> a >> b >> c;
        graph[a].push_back({b,c});
    }

    dijkstra(graph, distance, visited);

    for(int i = 1; i < n_cities + 1; ++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