Shortest Routes I

#include <bits/stdc++.h>

using namespace std;
#define int long long

// g++ <filename>.cpp -g -Wall -Wextra -DDEBUG -o <executable>

// copied from: https://codeforces.com/blog/entry/79024
// === Debug macro starts here ===

int recur_depth = 0;
#ifdef DEBUG
#define dbg(x) {++recur_depth; auto x_=x; --recur_depth; cerr<<string(recur_depth, '\t')<<"\e[91m"<<__func__<<":"<<__LINE__<<"\t"<<#x<<" = "<<x_<<"\e[39m"<<endl;}
#else
#define dbg(x)
#endif
template<typename Ostream, typename Cont>
typename enable_if<is_same<Ostream,ostream>::value, Ostream&>::type operator<<(Ostream& os,  const Cont& v){
	os<<"[";
	for(auto& x:v){os<<x<<", ";}
	return os<<"]";
}
template<typename Ostream, typename ...Ts>
Ostream& operator<<(Ostream& os,  const pair<Ts...>& p){
	return os<<"{"<<p.first<<", "<<p.second<<"}";
}

// === Debug macro ends here ===

#define INF LONG_MAX

vector<int> dijkstra(const vector<vector<pair<int, int>>>& adj, int start) {
    
    int n = adj.size();
    vector<int> dist(n, INF);
    dist[start] = 0;

    // store {distance, node} pairs
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, start});

    while (!pq.empty()) {
        int d = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        // skip node if distance is already less
        if (d > dist[u]) continue;

        // iterate thru neighbors
        for (const auto& edge : adj[u]) {
            int v = edge.first;
            int weight = edge.second;

            // relaxation step
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }

    return dist;
}

signed main() {
    
    int n, m; // cities, flight connections
    cin >> n >> m;

    vector<vector<pair<int, int>>> adj(n + 1);
    
    for (int i = 1; i <= m; i++) {
        int a,b,c;
        cin >> a >> b >> c;
        adj[a].push_back(make_pair(b,c));
    }

    // dbg(adj);

    vector<int> distances = dijkstra(adj, 1);

    for (int i = 1; i <= n; i++) {
        cout << distances[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: 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