src/opt/astar/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../util/alias/others/lib.hpp" | ||
| 4 | |||
| 5 | namespace tifa_libs { | ||
| 6 | |||
| 7 | template <class T> | ||
| 8 | requires requires(T x, T y) { | ||
| 9 | { x.solved() } -> std::same_as<bool>; | ||
| 10 | { x.next() } -> range; | ||
| 11 | x.cost() < y.cost(); | ||
| 12 | x < y; | ||
| 13 | } | ||
| 14 | 28 | auto astar(T CR s) NE { | |
| 15 | struct C { | ||
| 16 | 2994610 | CEXP bool operator()(cT_(T) a, cT_(T) b) CNE { return b.cost() < a.cost(); } | |
| 17 | }; | ||
| 18 | 28 | std::priority_queue<T, vec<T>, C> pq; | |
| 19 | 28 | std::set<T> vis; | |
| 20 | 28 | pq.push(s), vis.insert(s); | |
| 21 | 28 | std::optional<T> ret; | |
| 22 |
3/4✓ Branch 1 taken 164456 times.
✓ Branch 2 taken 28 times.
✓ Branch 4 taken 164484 times.
✗ Branch 5 not taken.
|
328968 | while (!pq.empty()) { |
| 23 | 164484 | T now = pq.top(); | |
| 24 |
2/2✓ Branch 2 taken 28 times.
✓ Branch 3 taken 164456 times.
|
164484 | if (pq.pop(); now.solved()) { |
| 25 | 28 | ret.emplace(now); | |
| 26 | 28 | return ret; | |
| 27 | } | ||
| 28 |
2/2✓ Branch 8 taken 270946 times.
✓ Branch 9 taken 164456 times.
|
435402 | for (auto nxt = now.next(); auto i : nxt) |
| 29 |
2/2✓ Branch 1 taken 231821 times.
✓ Branch 2 taken 39125 times.
|
270946 | if (!vis.count(i)) pq.push(i), vis.insert(i); |
| 30 | } | ||
| 31 | ✗ | return ret; | |
| 32 | 28 | } | |
| 33 | |||
| 34 | } // namespace tifa_libs | ||
| 35 |