dijkstra path

ソースコード

 1#include <vector>
 2#include <queue>
 3#include <algorithm>
 4using namespace std;
 5
 6// dijkstra_path
 7namespace titan23 {
 8
 9    template<typename T>
10    struct dijkstra_path {
11        int n;
12        T INF;
13        vector<int> prev;
14        vector<T> dist;
15
16        dijkstra_path() {}
17        dijkstra_path(vector<vector<pair<int, T>>> &G, int s, T INF) :
18                n(G.size()), INF(INF), prev(n, -1), dist(n, INF) {
19            dist[s] = 0;
20            priority_queue<pair<T, int>, vector<pair<T, int>>, greater<pair<T, int>>> hq;
21            hq.emplace(0, s);
22            while (!hq.empty()) {
23                auto [d, v] = hq.top();
24                hq.pop();
25                if (dist[v] < d) continue;
26                for (const auto &[x, c]: G[v]) {
27                    if (dist[x] > d + c) {
28                        dist[x] = d + c;
29                        prev[x] = v;
30                        hq.emplace(d+c, x);
31                    }
32                }
33            }
34        }
35
36        T get_dist(int t) const { return dist[t]; }
37
38        vector<int> get_path(int t) const {
39            vector<int> path;
40            if (dist[t] == INF) { return path; }
41            while (prev[t] != -1) {
42                path.emplace_back(t);
43                t = prev[t];
44            }
45            path.emplace_back(t);
46            reverse(path.begin(), path.end());
47            return path;
48        }
49    };
50}  // namespace titan23

仕様

Warning

doxygenfile: Cannot find file “titan_cpplib/graph/dijkstra_path.cpp