GCC Code Coverage Report

Directory: ./
File: tasks/nalitov_d_dijkstras_algorithm/seq/src/ops_seq.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 54 55 98.2%
Functions: 8 8 100.0%
Branches: 40 68 58.8%
Line Branch Exec Source
1 #include "nalitov_d_dijkstras_algorithm/seq/include/ops_seq.hpp"
2
3 #include <algorithm>
4 #include <cstddef>
5 #include <cstdint>
6 #include <limits>
7 #include <utility>
8 #include <vector>
9
10 #include "nalitov_d_dijkstras_algorithm/common/include/common.hpp"
11
12 namespace nalitov_d_dijkstras_algorithm {
13
14 namespace {
15
16 using OutgoingTable = std::vector<std::vector<std::pair<NodeId, Cost>>>;
17
18 bool CheckedSum(std::int64_t acc, Cost addend, std::int64_t &out) {
19 120 const auto x = static_cast<std::int64_t>(addend);
20
3/4
✓ Branch 0 taken 88 times.
✓ Branch 1 taken 32 times.
✓ Branch 2 taken 88 times.
✗ Branch 3 not taken.
 120 if (x > 0 && acc > std::numeric_limits<std::int64_t>::max() - x) {
21 return false;
22 }
23
1/4
✗ Branch 0 not taken.
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 32 if (x < 0 && acc < std::numeric_limits<std::int64_t>::min() - x) {
24 return false;
25 }
26 120 out = acc + x;
27 return true;
28 }
29
30 std::int64_t FindNextNode(const std::vector<Cost> &best, const std::vector<char> &visited) {
31 const auto vertex_count = best.size();
32 int best_c = kInf;
33 std::int64_t best_v = -1;
34
35
2/2
✓ Branch 0 taken 520 times.
✓ Branch 1 taken 120 times.
 640 for (std::size_t i = 0; i < vertex_count; ++i) {
36
4/4
✓ Branch 0 taken 320 times.
✓ Branch 1 taken 200 times.
✓ Branch 2 taken 120 times.
✓ Branch 3 taken 200 times.
 520 if (visited[i] == 0 && best[i] < best_c) {
37 best_c = best[i];
38 120 best_v = static_cast<std::int64_t>(i);
39 }
40 }
41 return best_v;
42 }
43
44 120 void RelaxNeighborsSeq(std::size_t u, Cost u_dist, const OutgoingTable &graph, std::vector<Cost> &best,
45 const std::vector<char> &visited) {
46
2/2
✓ Branch 0 taken 96 times.
✓ Branch 1 taken 120 times.
 216 for (const auto &neighbor : graph[u]) {
47 96 const NodeId v = neighbor.first;
48 96 const Cost w = neighbor.second;
49
1/2
✓ Branch 0 taken 96 times.
✗ Branch 1 not taken.
 96 const auto vi = static_cast<std::size_t>(v);
50
51
3/6
✓ Branch 0 taken 96 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 96 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 96 times.
✗ Branch 5 not taken.
 96 if (visited[vi] == 0 && u_dist <= kInf - w && u_dist + w < best[vi]) {
52 96 best[vi] = u_dist + w;
53 }
54 }
55 120 }
56
57 32 std::vector<Cost> FindShortestPaths(NodeId start, const OutgoingTable &graph) {
58 const auto vertex_count = graph.size();
59 32 std::vector<Cost> best(vertex_count, kInf);
60
1/4
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 32 std::vector<char> visited(vertex_count, 0);
61
62 32 best[static_cast<std::size_t>(start)] = 0;
63
64
2/2
✓ Branch 0 taken 120 times.
✓ Branch 1 taken 32 times.
 152 for (std::size_t step = 0; step < vertex_count; ++step) {
65 std::int64_t u = FindNextNode(best, visited);
66
1/2
✓ Branch 0 taken 120 times.
✗ Branch 1 not taken.
 120 if (u == -1) {
67 break;
68 }
69
70 120 const auto ui = static_cast<std::size_t>(u);
71 120 visited[ui] = 1;
72
73 120 RelaxNeighborsSeq(ui, best[ui], graph, best, visited);
74 }
75
76 32 return best;
77 }
78
79 32 bool AccumulateFiniteDistances(const std::vector<Cost> &best, OutType &sum) {
80 std::int64_t acc = 0;
81
2/2
✓ Branch 0 taken 120 times.
✓ Branch 1 taken 32 times.
 152 for (Cost d : best) {
82
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 120 times.
 120 if (d == kInf) {
83 ✗ continue;
84 }
85 if (!CheckedSum(acc, d, acc)) {
86 return false;
87 }
88 }
89
1/2
✓ Branch 0 taken 32 times.
✗ Branch 1 not taken.
 32 if (acc < 0 || acc > std::numeric_limits<OutType>::max()) {
90 return false;
91 }
92 32 sum = acc;
93 32 return true;
94 }
95
96 } // namespace
97
98
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 NalitovDDijkstrasAlgorithmSeq::NalitovDDijkstrasAlgorithmSeq(const InType &in) {
99 SetTypeOfTask(GetStaticTypeOfTask());
100 GetInput() = in;
101 32 GetOutput() = 0;
102 32 }
103
104 32 bool NalitovDDijkstrasAlgorithmSeq::ValidationImpl() {
105
1/2
✓ Branch 0 taken 32 times.
✗ Branch 1 not taken.
 32 if (GetOutput() != 0) {
106 return false;
107 }
108
109 const InType &in = GetInput();
110 constexpr int kMaxVertices = 10000;
111
3/6
✓ Branch 0 taken 32 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 32 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 32 times.
✗ Branch 5 not taken.
 32 if (in.n <= 0 || in.n > kMaxVertices || in.source < 0 || in.source >= in.n) {
112 return false;
113 }
114
115 const auto arc_ok = [&in](const Arc &a) {
116
5/10
✓ Branch 0 taken 96 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 96 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 96 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 96 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 96 times.
✗ Branch 9 not taken.
 96 return a.from >= 0 && a.to >= 0 && a.from < in.n && a.to < in.n && a.weight >= 0;
117 };
118 return std::ranges::all_of(in.arcs, arc_ok);
119 }
120
121 32 bool NalitovDDijkstrasAlgorithmSeq::PreProcessingImpl() {
122 const InType &in = GetInput();
123 32 graph_.assign(static_cast<std::size_t>(in.n), {});
124
125
2/2
✓ Branch 0 taken 96 times.
✓ Branch 1 taken 32 times.
 128 for (const Arc &a : in.arcs) {
126 96 graph_[static_cast<std::size_t>(a.from)].emplace_back(a.to, a.weight);
127 }
128 32 GetOutput() = 0;
129 32 return true;
130 }
131
132
1/2
✓ Branch 0 taken 32 times.
✗ Branch 1 not taken.
 32 bool NalitovDDijkstrasAlgorithmSeq::RunImpl() {
133 const InType &in = GetInput();
134
1/2
✓ Branch 0 taken 32 times.
✗ Branch 1 not taken.
 32 if (graph_.size() != static_cast<std::size_t>(in.n)) {
135 return false;
136 }
137
138 32 const std::vector<Cost> best = FindShortestPaths(in.source, graph_);
139
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 32 times.
 32 if (best.size() != static_cast<std::size_t>(in.n)) {
140 return false;
141 }
142
143 32 OutType total = 0;
144
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 32 times.
 32 if (!AccumulateFiniteDistances(best, total)) {
145 return false;
146 }
147 32 GetOutput() = total;
148 32 return true;
149 }
150
151 32 bool NalitovDDijkstrasAlgorithmSeq::PostProcessingImpl() {
152 32 return GetOutput() >= 0;
153 }
154
155 } // namespace nalitov_d_dijkstras_algorithm
156