Shortest Routes I

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

typedef long long ll;
typedef pair<ll, ll> P;
typedef vector<vector<P>> graph;
typedef pair<ll, ll> P;

void read(graph &g, ll m) {
    for (ll i = 0; i < m; ++i) {
        ll u, v, c;
        cin >> u >> v >> c;
        g[u-1].push_back(make_pair(c,v-1));
    }
}

vector<ll> dijkstra(const graph& g, ll ini) {

    ll n = g.size();
    vector<ll> dist(n, LLONG_MAX);
    vector<bool> vis(n, false);
    priority_queue<P, vector<P>, greater<P>> pq;

    dist[ini] = 0;
    pq.push(P(0,ini));


    while(not pq.empty()) {
        ll node = pq.top().second;
        pq.pop();

        if (not vis[node]) {
            vis[node] = true;
            for (ll i = 0; i < ll(g[node].size()); ++i) {
                ll desti = g[node][i].second;
                ll cost = g[node][i].first;
                if (dist[desti] > dist[node]+cost) {
                    dist[desti] = dist[node] + cost;
                    pq.push({dist[desti], desti});
                }

            }
        }
    }

    return dist;
}

void print_vector(vector<ll> &v) {
    ll n = v.size();
    for (ll i = 0; i < n; ++i)
        cout << v[i] << " ";
    cout << endl;
}

int main() {
    ll n, m;
    cin >> n >> m;

    graph g(n);
    read(g, m);

    vector<ll> distances = dijkstra(g, 0);

    print_vector(distances);
}

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