Untitled

// --------------------------------------------------<TEMPLATE>-------------------------------------------------- 
// --------------------<optimizations>-------------------- 
 
/* 
#pragma GCC optimize("Ofast,unroll-loops") 
#pragma GCC target("avx,avx2,fma") 
*/  

// ---------------</HEADERS and NAMESPACES>--------------- 
#include <bits/stdc++.h>
#define ff                      first
#define ss                      second
#define tt                      third
#define mt                      make_tuple
#define pb                      push_back
#define forn(i, j, k, in)       for (int i = j; i < k; i += in)
#define rfor(i, j, k, in)       for (int i = j; i >= k; i -= in)
#define fora(x, a)              for (auto &x : a)
#define sz(a)                   int((a).size()) 
#define all(cont)               cont.begin(), cont.end()
using namespace std;

// >
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<pii> vii;
typedef vector<vi> vvi;
typedef map<int, int> mpii;
typedef set<int> seti;
typedef tuple<int, int, int> Node;

// >
typedef long int int32;
typedef unsigned long int uint32;
typedef long long int int64;
typedef unsigned long long int uint64;

// ------------------</DEBUGGING STUFF>------------------- 
#define debug(x)        cout << '>' << #x << ':' << x << endl;

// ----<PRINTF>----- 
#define pf              printf 
#define pfi(x)          printf("%d\n",x); 
#define pfi2(x,y)       printf("%d %d\n",x,y); 
#define pfi3(x,y,z)     printf("%d %d %d\n",x,y,z); 

template <class T>
void print_v(vector<T> &v) { cout << "{ "; fora(x,v) cout << x << " "; cout << "\b}" << endl; }

tuple<int,int> dijkstra(int n, int src, int dst, vi &parent, vi &dist,
             map<int, vii> &adj) {
        seti visited;
        priority_queue<Node, vector<Node>, greater<Node>> pq; // min heap
        pq.push(mt(0,0,src));

        while (!pq.empty()) {
                auto [node_dist, steps, node] = pq.top();
                pq.pop();

                if (node == dst) return mt(node_dist,steps);
                visited.insert(node);

                fora(nei, adj[node]) {
                        auto [new_node, new_dist] = nei;
                        int curr_dist = node_dist + new_dist;

                        if (visited.find(new_node) == visited.end() &&
                            curr_dist < dist[new_node]) {
                                dist[new_node] = curr_dist;
                                parent[new_node] = node;
                                pq.push(mt(curr_dist, steps + 1, new_node));
                        }
                }
        }
        return mt(-1,-1);
}

void print_path(vector<int> &parent, int destination) {
        vi path;
        int current = destination;
        while (current != -1) {
                path.pb(current);
                current = parent[current];
        }

        reverse(all(path));
        cout << "path: ";
        print_v(path);
}

int main() {
        map<int, vii> adj = {{0, {{1, 200}, {2, 50}}},
                                       {1, {{2, 100}}},
                                       {2, {{3, 100}}},
                                       {3, {}}};
        int dst = 2;
        int n = sz(adj);
        vi dist, parent;
        dist.pb(0);
        forn(i, 0, n, 1) {
                dist.pb(INT_MAX);
                parent.pb(-1);
        }

        auto [cost, stopped_cities] = dijkstra(n, 0, dst, parent, dist, adj);
        cout << "cost = " << cost << " => stopped at " << stopped_cities << " cities " << endl;
        print_path(parent, dst);
        cout << "parent: ";
        print_v(parent);
        return 0;
}