| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include <vector> | ||
| 4 | |||
| 5 | #include "potashnik_m_short_ways_bellford/common/include/common.hpp" | ||
| 6 | #include "task/include/task.hpp" | ||
| 7 | |||
| 8 | namespace potashnik_m_short_ways_bellford { | ||
| 9 | |||
| 10 | class PotashnikMShortWaysBellfordSEQ : public BaseTask { | ||
| 11 | public: | ||
| 12 | static constexpr ppc::task::TypeOfTask GetStaticTypeOfTask() { | ||
| 13 | return ppc::task::TypeOfTask::kSEQ; | ||
| 14 | } | ||
| 15 | explicit PotashnikMShortWaysBellfordSEQ(const InType &in); | ||
| 16 | |||
| 17 | private: | ||
| 18 | bool ValidationImpl() override; | ||
| 19 | bool PreProcessingImpl() override; | ||
| 20 | bool RunImpl() override; | ||
| 21 | bool PostProcessingImpl() override; | ||
| 22 | }; | ||
| 23 | |||
| 24 | 936 | inline void BellmanFordAlgoIterationSeq(const Graph &g, const std::vector<int> &dist, std::vector<int> &dist_next) { | |
| 25 | 936 | int n = g.n; | |
| 26 | 936 | dist_next = dist; | |
| 27 |
2/2✓ Branch 0 taken 13356 times.
✓ Branch 1 taken 936 times.
|
14292 | for (int uidx = 0; uidx < n; uidx++) { |
| 28 |
2/2✓ Branch 0 taken 4392 times.
✓ Branch 1 taken 8964 times.
|
13356 | if (dist[uidx] == 1e9) { |
| 29 | 4392 | continue; | |
| 30 | } | ||
| 31 | 8964 | IterateThroughVertex(g, uidx, dist, dist_next); | |
| 32 | } | ||
| 33 | 936 | } | |
| 34 | |||
| 35 | 90 | inline void BellmanFordAlgoSeq(const Graph &g, int source, std::vector<int> &dist) { | |
| 36 | 90 | int n = g.n; | |
| 37 | |||
| 38 | // Compiler wont let it work without this lines (This should be just a warning, but I can't not fix it with this) | ||
| 39 |
1/2✓ Branch 0 taken 90 times.
✗ Branch 1 not taken.
|
90 | if (n == 0) { |
| 40 | ✗ | return; | |
| 41 | } | ||
| 42 |
1/2✓ Branch 0 taken 90 times.
✗ Branch 1 not taken.
|
90 | if (source < 0 || source >= n) { |
| 43 | return; | ||
| 44 | } | ||
| 45 | |||
| 46 | 90 | dist.assign(n, 1e9); | |
| 47 | 90 | dist[source] = 0; | |
| 48 | |||
| 49 | 90 | std::vector<int> dist_next(n); | |
| 50 | |||
| 51 |
2/2✓ Branch 0 taken 936 times.
✓ Branch 1 taken 90 times.
|
1026 | for (int i = 0; i < n - 1; i++) { |
| 52 |
1/2✓ Branch 1 taken 936 times.
✗ Branch 2 not taken.
|
936 | BellmanFordAlgoIterationSeq(g, dist, dist_next); |
| 53 | dist.swap(dist_next); | ||
| 54 | } | ||
| 55 | } | ||
| 56 | |||
| 57 | } // namespace potashnik_m_short_ways_bellford | ||
| 58 |