src/graph/sp/floyd/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../../util/traits/math/lib.hpp" | ||
| 4 | #include "../../ds/amat/lib.hpp" | ||
| 5 | |||
| 6 | namespace tifa_libs { | ||
| 7 | |||
| 8 | //! will change input graph | ||
| 9 | // @return false if invalid (has negative cycle), otherwise true | ||
| 10 | template <class T> | ||
| 11 | 50 | CEXP bool floyd(amat<T>& g, T INF = inf_v<T>) NE { | |
| 12 | 50 | cu32 n = g.vsize(); | |
| 13 |
2/2✓ Branch 0 taken 2276 times.
✓ Branch 1 taken 50 times.
|
2326 | flt_ (u32, k, 0, n) |
| 14 |
2/2✓ Branch 0 taken 171846 times.
✓ Branch 1 taken 2276 times.
|
174122 | flt_ (u32, x, 0, n) |
| 15 |
2/2✓ Branch 1 taken 97733 times.
✓ Branch 2 taken 74113 times.
|
171846 | if (g.val(x, k) < INF) |
| 16 |
2/2✓ Branch 0 taken 8547844 times.
✓ Branch 1 taken 97733 times.
|
8645577 | flt_ (u32, y, 0, n) |
| 17 |
2/2✓ Branch 1 taken 5381170 times.
✓ Branch 2 taken 3166674 times.
|
8547844 | if (g.val(k, y) < INF) g.set_val(x, y, min(g.val(x, y), g.val(x, k) + g.val(k, y))); |
| 18 | if CEXP (sint_c<T>) | ||
| 19 |
2/2✓ Branch 0 taken 2113 times.
✓ Branch 1 taken 43 times.
|
2156 | flt_ (u32, x, 0, n) |
| 20 |
2/2✓ Branch 1 taken 7 times.
✓ Branch 2 taken 2106 times.
|
2113 | if (g.val(x, x) < 0) return false; |
| 21 | 43 | return true; | |
| 22 | } | ||
| 23 | |||
| 24 | } // namespace tifa_libs | ||
| 25 |