Untitled

#include <bits/stdc++.h>

#define ff first
#define ss second
#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 debug(x) cout << '>' << #x << ':' << x << endl;
#define all(cont) cont.begin(), cont.end()

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 long int int32;
typedef unsigned long int uint32;
typedef long long int int64;
typedef unsigned long long int uint64;

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

using namespace std;

int dijkstra(int n, int src, int dst, vi &parent, vi &dist,
             map<int, vii> &adj) {
        seti visited;
        priority_queue<pii> pq;
        pq.push({0, src});

        while (!pq.empty()) {
                int node_dist = pq.top().ff * -1;
                int node = pq.top().ss;
                pq.pop();

                if (node == dst) return node_dist;
                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({-curr_dist, new_node});
                        }
                }
        }
        return -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> adjacencyList = {{0, {{1, 200}, {2, 50}}},
                                       {1, {{2, 100}}},
                                       {2, {{3, 100}}},
                                       {3, {}}};
        int n = adjacencyList.size();
        vi dist, parent;
        dist.pb(0);
        forn(i, 0, n, 1) {
                dist.pb(INT_MAX);
                parent.pb(-1);
        }

        int cost = dijkstra(n, 0, 3, parent, dist, adjacencyList);
        cout << "cost = " << cost << endl;
        print_path(parent, 3);
        cout << "parent: ";
        print_v(parent);
        return 0;
}