src/graph/sp/johnson/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../ds/alist/lib.hpp" | ||
| 4 | #include "../bm/lib.hpp" | ||
| 5 | #include "../dijkstra/lib.hpp" | ||
| 6 | |||
| 7 | namespace tifa_libs { | ||
| 8 | |||
| 9 | // @return dis, with dis[u][v] = minimum distance between u and v | ||
| 10 | template <class T> | ||
| 11 | 50 | CEXP auto johnson(u32 n, vec<edge_t<T>> CR arcs, T const INF = inf_v<T>) NE { | |
| 12 | using U = to_uint_t<T>; | ||
| 13 | 50 | std::optional<vvec<T>> ret; | |
| 14 | |||
| 15 | if CEXP (!sint_c<T>) { | ||
| 16 | alist<T> g(n); | ||
| 17 | for (auto [w, u, v] : arcs) g.add_arc(u, v, w); | ||
| 18 | ret->emplace(vvec<T>(n)); | ||
| 19 | flt_ (u32, i, 0, n) ret.value()[i] = dijkstra(g, i, fn_0, INF); | ||
| 20 | } else { | ||
| 21 | 50 | alist<T> g(n + 1); | |
| 22 |
2/2✓ Branch 6 taken 36464 times.
✓ Branch 7 taken 50 times.
|
36514 | for (auto [w, u, v] : arcs) g.add_arc(u, v, w); |
| 23 |
2/2✓ Branch 1 taken 2276 times.
✓ Branch 2 taken 50 times.
|
2326 | flt_ (u32, i, 0, n) g.add_arc(n, i, 0); |
| 24 | 50 | auto h = bellman_ford(g, n, fn_0, INF); | |
| 25 |
2/2✓ Branch 1 taken 7 times.
✓ Branch 2 taken 43 times.
|
50 | if (!h) return ret; |
| 26 | 43 | ret.emplace(vvec<T>(n)); | |
| 27 | 43 | alist<U> fg2(n); | |
| 28 |
2/2✓ Branch 10 taken 35852 times.
✓ Branch 11 taken 43 times.
|
35895 | for (auto [w, u, v] : arcs) fg2.add_arc(u, v, U(w - h.value()[v] + h.value()[u])); |
| 29 |
2/2✓ Branch 1 taken 2103 times.
✓ Branch 2 taken 43 times.
|
2146 | flt_ (u32, i, 0, n) { |
| 30 | 2103 | auto dis2 = dijkstra(fg2, i, fn_0, (U)INF); | |
| 31 | 2103 | ret.value()[i].resize(n); | |
| 32 |
4/4✓ Branch 1 taken 117301 times.
✓ Branch 2 taken 43056 times.
✓ Branch 11 taken 160357 times.
✓ Branch 12 taken 2103 times.
|
162460 | flt_ (u32, j, 0, n) ret.value()[i][j] = dis2[j] == (U)INF ? INF : (T)dis2[j] + h.value()[j] - h.value()[i]; |
| 33 | } | ||
| 34 |
4/4✓ Branch 2 taken 43 times.
✓ Branch 3 taken 7 times.
✓ Branch 5 taken 43 times.
✓ Branch 6 taken 7 times.
|
57 | } |
| 35 | 43 | return ret; | |
| 36 | } | ||
| 37 | |||
| 38 | } // namespace tifa_libs | ||
| 39 |