warshall floyd path

ソースコード

 1#include <vector>
 2using namespace std;
 3
 4// warshall_floyd_path
 5namespace titan23 {
 6
 7template<typename T>
 8class warshall_floyd_path {
 9  private:
10    int n;
11    T INF;
12    vector<int> nxt;
13    vector<T> dist;
14
15  public:
16    warshall_floyd_path() {}
17
18    // 時間 O(|V|^3), 空間 O(|V|^2)
19    warshall_floyd_path(const vector<vector<pair<int, T>>> &G, const T INF) :
20            n(G.size()), INF(INF), nxt(n*n), dist(n*n, INF) {
21        for (int v = 0; v < n; ++v) {
22            for (int x = 0; x < n; ++x) {
23                nxt[v*n+x] = x;
24            }
25            for (const auto &[x, c]: G[v]) {
26                dist[v*n+x] = min(dist[v*n+x], c);
27            }
28            dist[v*n+v] = 0;
29        }
30        for (int k = 0; k < n; ++k) {
31            for (int i = 0; i < n; ++i) {
32                T dik = dist[i*n+k];
33                if (dik == INF) continue;
34                for (int j = 0; j < n; ++j) {
35                    if (dist[k*n+j] == INF) continue;
36                    if (dist[i*n+j] > dik + dist[k*n+j]) {
37                    dist[i*n+j] = dik + dist[k*n+j];
38                    nxt[i*n+j] = nxt[i*n+k];
39                    }
40                }
41            }
42        }
43    }
44
45    // O(1)
46    T get_dist(const int s, const int t) const {
47        return dist[s*n+t];
48    }
49
50    // O(|path|)
51    vector<int> get_path(int s, int t) const {
52        vector<int> path;
53        if (dist[s*n+t] == INF) { return path; }
54        for (; s != t; s = nxt[s*n+t]) {
55            path.emplace_back(s);
56        }
57        path.emplace_back(t);
58        return path;
59    }
60};
61}  // namespace titan23

仕様

Warning

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