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

namespace template_algorithm {
    /// @brief ダイクストラ法(クラス)
    /// @attention 求められるものは「startからの」最短経路。 求める際は0-indexedにすること。
    template<typename T>
    class dijkstra{
        public:
        /// @brief 辺クラス
        class edge{
            public:
            int to;
            T cost;
        };

        /// @brief コンストラクタ
        /// @param n_ 頂点数
        /// @param start_ スタート地点(source)(0-indexed)
        dijkstra(int n_, int start_) {
            n = n_;
            INF = numeric_limits<T>::max();
            adj_list.assign(n, vector<edge>());
            set_start(start_);
        }

        /// @brief ソース(始点)、配列の初期化
        void set_start(int start_) {
            start = start_;
            shortest_path.assign(n, INF);
            prev_node.assign(n, -1);
        }

        /// @brief fromからtoに重みcostの辺を追加
        void add_edge(int from, int to, T cost){
            adj_list[from].push_back({to, cost});
        }

        /// @brief このクラス内の隣接リストを使った最短経路計算
        vector<T> search_shortest_path() {
            return culc_shortest_path(adj_list);
        }

        /// @brief このクラス外から与えられた隣接リストを使った最短経路計算
        vector<T> search_shortest_path(const vector<vector<edge> > &arg_adj) {
            return culc_shortest_path(arg_adj);
        }

        /// @brief 頂点startからのtoまでの最短距離を返します
        T get_shortest_path(int to) {
            return shortest_path[to];
        }

        /// @brief toまでの具体的な経路を返します
        vector<int> get_concrete_path(int to) {
            vector<int> concrete_path;
            for (int i = to; i != -1; i = prev_node[i]) {
                concrete_path.push_back(i);
            }
            reverse(concrete_path.begin(), concrete_path.end());
            return concrete_path;
        }

        private:
        int n;
        int start;
        T INF;
        vector<vector<edge> > adj_list;
        vector<T> shortest_path;
        vector<int> prev_node;

        /// @brief 最短経路の計算
        vector<T> culc_shortest_path(const vector<vector<edge> > &arg_adj) {
            //tuple   <0> := コスト <1>:= 頂点番号 <2>:= どの頂点から来たか
            priority_queue<tuple<T, int, int>, vector<tuple<T, int, int> >, greater<tuple<T, int, int> > > pq;
            pq.push({0, start, -1});

            while (!pq.empty()) {
                tuple<T, int, int> t = pq.top();
                pq.pop();

                //現在のノードまでのコスト
                T cost;
                //現在の頂点
                int now_v;
                //ひとつ前の頂点
                int prev_v;
                tie(cost, now_v, prev_v) = t;

                //すでに確定している
                if (shortest_path[now_v] != INF) continue;

                //最短距離を確定
                shortest_path[now_v] = cost;

                //ひとつ前の頂点を記録
                prev_node[now_v] = prev_v;

                //確定した頂点から出ている辺すべてについて、調べる候補に追加
                for (auto &e : arg_adj[now_v]) {
                    //よりコストが増える場合は飛ばしてよい
                    if (shortest_path[e.to] < cost + e.cost) continue;
                    pq.push({cost + e.cost, e.to, now_v});
                }
            }
            return shortest_path;
        }
    };
}