ダイクストラ法のテンプレ~経路復元可(C++)

namespace template_algorithm {
    namespace dijkstra_algorithm {
        /** @brief 辺クラス */
        template <typename cost_type>
        class edge {
        public:
            /** @brief default constructor */
            edge() = default;
            /** 
             * @brief constructor
             * 行き先:to, 重み:costの辺を生成する
             */
            edge(int to, cost_type cost) : to(to), cost(cost) {}

            /** @brief toのgetter */
            const int& get_to() const { return to; }

            /** @brief costのgetter*/
            const cost_type& get_cost() const { return cost; }

        private:
            int to;
            cost_type cost;
        };

        /** @brief グラフクラス */
        template <typename cost_type>
        class graph {
        public:
            /** @brief default constructor */
            graph() = default;
            /** @brief constructor
             *  ノード数node_countのグラフを生成する
             */
            explicit graph(int node_count) : node_count(node_count), adjacency_list(std::vector<std::vector<edge<cost_type> > >(node_count, std::vector<edge<cost_type> >())) {}

            /** @brief 有向辺を追加する */
            void add_directed_edge(int from_u, int to_v, cost_type cost) {
                adjacency_list[from_u].push_back(edge(to_v, cost));
            }

            /** @brief 無向辺を追加する */
            void add_undirected_edge(int u, int v, cost_type cost) {
                adjacency_list[u].push_back(edge(v, cost));
                adjacency_list[v].push_back(edge(u, cost));
            }

            /** @brief node_countのgetter */
            const int& get_node_count() const { return node_count; }

            /** @brief fromから出ている辺集合を取得する */
            const std::vector<edge<cost_type> >& get_adjacent_edges(int from) const { return adjacency_list[from]; }

        private:
            int node_count;
            std::vector<std::vector<edge<cost_type> > > adjacency_list;
        };

        /** @brief ダイクストラ法クラス */
        template <typename cost_type>
        class dijkstra {
        public:
            /** @brief default constructor */
            dijkstra() = default;
            /** 
             * @brief constructor
             * この時点で与えられた{スタート地点, グラフ}での最短経路問題を解き
             * 計算結果をこのクラスに保持する
             */
            dijkstra(int start, const graph<cost_type>& g)
                : shortest_distances(std::vector<cost_type>(g.get_node_count(), INF)), previous_nodes(std::vector<int>(g.get_node_count(), INVALID_PREVIOUS_NUMBER)) {
                std::priority_queue<move_candidates, std::vector<move_candidates>, std::greater<move_candidates> > pq;
                pq.push(move_candidates(start, 0, INVALID_PREVIOUS_NUMBER));

                while (!pq.empty()) {
                    move_candidates mc = pq.top();
                    pq.pop();

                    const int& now_node = mc.get_node_index();
                    const cost_type& now_cost = mc.get_cost();
                    const int& now_previous_node = mc.get_previous_node();

                    if (shortest_distances[now_node] != INF) continue;

                    shortest_distances[now_node] = now_cost;
                    previous_nodes[now_node] = now_previous_node;

                    for (const auto& e : g.get_adjacent_edges(now_node)) {
                        if (shortest_distances[e.get_to()] != INF) continue;
                        pq.push(move_candidates(e.get_to(), shortest_distances[now_node] + e.get_cost(), now_node));
                    }
                }
            }

            /** 
             * @brief 到達可能かどうかを取得する
             * @return true:可能 false:不可能
             */
            bool is_reachable(int to) { return shortest_distances[to] != INF; }

            /** @brief スタート地点からの最短距離を取得する */
            const cost_type& get_shortest_distance(int to) const {
                return shortest_distances[to];
            }

            /** @brief toまでの具体的な最短経路を復元して取得する */
            std::vector<int> get_shortest_path(int to) const {
                std::vector<int> path;
                for (int now = to; now != INVALID_PREVIOUS_NUMBER; now = previous_nodes[now]) path.push_back(now);
                std::ranges::reverse(path);
                return path;
            }
            
        private:
            /** @brief 移動候補クラス */
            class move_candidates {
            public:
                /** @brief default constructor */
                move_candidates() = default;
                /** @brief constructor
                 *  {移動先:node_index, コスト:cost, 直前にいた頂点:previous_node}として移動候補を生成する
                 */
                move_candidates(int node_index, cost_type cost, int previous_node) : node_index(node_index), cost(cost), previous_node(previous_node) {}

                /** @brief costの大きさで比較する演算子overload */
                bool operator>(const move_candidates &other) const {
                    return cost > other.cost;
                }

                /** @brief node_indexのgetter */
                const int& get_node_index() const { return node_index; }

                /** @brief costのgetter */
                const cost_type& get_cost() const { return cost; }

                /** @brief previous_nodeのgetter */
                const int& get_previous_node() const { return previous_node; }

            private:
                int node_index;
                cost_type cost;

                int previous_node;
            };

            const cost_type INF = std::numeric_limits<cost_type>::max();
            std::vector<cost_type> shortest_distances;

            const int INVALID_PREVIOUS_NUMBER = -1;
            std::vector<int> previous_nodes;
        };
    } 
}

//コストがint型で表せる、ノード数がnのグラフを生成
template_algorithm::dijkstra_algorithm::graph<int> g(n);

/*
頂点{a, b}を結ぶ重みcの無向辺をm回追加する例
*/
for (int i = 0; i < m; i++) {
    int a, b;
    ll c;
    std::cin >> a >> b >> c;

    //無向辺を追加
    g.add_undirected_edge(a, b, c);

    //有向辺(a->b)ならこっちを使う
    //add_directed_edge(a, b, c);
}

//重みの和がint型におさまる範囲、かつスタート地点が0でグラフgを使った場合の例
template_algorithm::dijkstra_algorithm::dijkstra<int> dj(0, g);