#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"
#include <cassert>
#include <iostream>
#include <vector>
#include "../../graph/dijkstra.hpp"
#include "../../graph/graph.hpp"
struct Cost {
long long value = 0;
Cost operator+(const Cost& other) const {
return Cost{value + other.value};
}
friend bool operator<(const Cost& first, const Cost& second) {
return first.value < second.value;
}
};
void test_custom_cost() {
m1une::graph::Graph<Cost> graph(6);
graph.add_directed_edge(0, 1, Cost{8});
graph.add_directed_edge(0, 2, Cost{2});
graph.add_directed_edge(2, 1, Cost{3});
graph.add_directed_edge(1, 3, Cost{4});
graph.add_directed_edge(2, 3, Cost{20});
graph.add_directed_edge(4, 3, Cost{1});
auto result = m1une::graph::dijkstra(graph, 0);
assert(result.reachable(0));
assert(result.reachable(3));
assert(!result.reachable(4));
assert(!result.reachable(5));
assert(result.dist[0].value == 0);
assert(result.dist[1].value == 5);
assert(result.dist[3].value == 9);
assert((result.path(3) == std::vector<int>{0, 2, 1, 3}));
auto multi = m1une::graph::dijkstra(
graph, std::vector<int>{0, 4, 0});
assert(multi.reachable(4));
assert(multi.dist[3].value == 1);
assert((multi.path(3) == std::vector<int>{4, 3}));
}
void test_explicit_sentinel_is_not_reachability() {
m1une::graph::Graph<Cost> graph(3);
graph.add_directed_edge(0, 1, Cost{99});
auto result = m1une::graph::dijkstra(graph, 0, Cost{99});
assert(result.inf.value == 99);
assert(result.reachable(1));
assert(result.dist[1].value == 99);
assert(!result.reachable(2));
assert(result.dist[2].value == 99);
}
int main() {
test_custom_cost();
test_explicit_sentinel_is_not_reachability();
long long a, b;
std::cin >> a >> b;
std::cout << a + b << '\n';
}
#line 1 "verify/graph/dijkstra_custom_cost.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"
#include <cassert>
#include <iostream>
#include <vector>
#line 1 "graph/dijkstra.hpp"
#include <algorithm>
#line 6 "graph/dijkstra.hpp"
#include <utility>
#line 8 "graph/dijkstra.hpp"
#line 1 "graph/graph.hpp"
#include <array>
#line 8 "graph/graph.hpp"
namespace m1une {
namespace graph {
template <class T = int>
struct Edge {
using cost_type = T;
int from;
int to;
T cost;
int id;
bool alive;
Edge() : from(-1), to(-1), cost(T()), id(-1), alive(true) {}
Edge(int from_, int to_, T cost_ = T(1), int id_ = -1, bool alive_ = true)
: from(from_), to(to_), cost(cost_), id(id_), alive(alive_) {}
int other(int v) const {
assert(v == from || v == to);
return from ^ to ^ v;
}
};
template <class T = int>
struct Graph {
using edge_type = Edge<T>;
using cost_type = T;
private:
struct EdgePositions {
std::array<std::pair<int, int>, 2> value{};
int size = 0;
void push_back(std::pair<int, int> position) {
assert(size < 2);
value[size++] = position;
}
};
int _n;
int _edge_count;
std::vector<std::vector<edge_type>> _g;
std::vector<EdgePositions> _edge_positions;
public:
Graph() : _n(0), _edge_count(0) {}
explicit Graph(int n) : _n(n), _edge_count(0), _g(n) {
assert(0 <= n);
}
int size() const {
return _n;
}
bool empty() const {
return _n == 0;
}
int edge_count() const {
return _edge_count;
}
int add_vertex() {
_g.emplace_back();
return _n++;
}
int add_directed_edge(int from, int to, T cost = T(1)) {
assert(0 <= from && from < _n);
assert(0 <= to && to < _n);
int id = _edge_count++;
int idx = int(_g[from].size());
_g[from].push_back(edge_type(from, to, cost, id));
_edge_positions.emplace_back();
_edge_positions.back().push_back({from, idx});
return id;
}
int add_edge(int u, int v, T cost = T(1)) {
assert(0 <= u && u < _n);
assert(0 <= v && v < _n);
int id = _edge_count++;
int u_idx = int(_g[u].size());
_g[u].push_back(edge_type(u, v, cost, id));
int v_idx = int(_g[v].size());
_g[v].push_back(edge_type(v, u, cost, id));
_edge_positions.emplace_back();
_edge_positions.back().push_back({u, u_idx});
_edge_positions.back().push_back({v, v_idx});
return id;
}
void set_edge_alive(int id, bool alive) {
assert(0 <= id && id < _edge_count);
for (int i = 0; i < _edge_positions[id].size; ++i) {
auto [v, idx] = _edge_positions[id].value[i];
_g[v][idx].alive = alive;
}
}
void erase_edge(int id) {
set_edge_alive(id, false);
}
void revive_edge(int id) {
set_edge_alive(id, true);
}
bool is_edge_alive(int id) const {
assert(0 <= id && id < _edge_count);
assert(_edge_positions[id].size != 0);
auto [v, idx] = _edge_positions[id].value[0];
return _g[v][idx].alive;
}
const std::vector<edge_type>& operator[](int v) const {
assert(0 <= v && v < _n);
return _g[v];
}
std::vector<edge_type>& operator[](int v) {
assert(0 <= v && v < _n);
return _g[v];
}
const std::vector<std::vector<edge_type>>& adjacency() const {
return _g;
}
std::vector<std::vector<edge_type>>& adjacency() {
return _g;
}
std::vector<edge_type> edges(bool include_inactive = false) const {
std::vector<edge_type> result;
result.reserve(_edge_count);
std::vector<char> used(_edge_count, false);
for (int v = 0; v < _n; v++) {
for (const auto& e : _g[v]) {
if (!include_inactive && !e.alive) continue;
if (0 <= e.id && e.id < _edge_count) {
if (used[e.id]) continue;
used[e.id] = true;
}
result.push_back(e);
}
}
return result;
}
Graph reversed() const {
Graph result(_n);
result._edge_count = _edge_count;
result._edge_positions.assign(_edge_count, {});
for (int v = 0; v < _n; v++) {
for (const auto& e : _g[v]) {
int idx = int(result._g[e.to].size());
result._g[e.to].push_back(edge_type(e.to, e.from, e.cost, e.id, e.alive));
if (0 <= e.id && e.id < _edge_count) result._edge_positions[e.id].push_back({e.to, idx});
}
}
return result;
}
};
} // namespace graph
} // namespace m1une
#line 10 "graph/dijkstra.hpp"
namespace m1une {
namespace graph {
template <class T>
struct DijkstraResult {
std::vector<T> dist;
std::vector<char> reached;
std::vector<int> parent;
std::vector<int> parent_edge;
T inf = T();
bool reachable(int v) const {
assert(0 <= v && v < int(dist.size()));
return reached[v];
}
std::vector<int> path(int t) const {
assert(reachable(t));
std::vector<int> result;
for (int v = t; v != -1; v = parent[v]) result.push_back(v);
std::reverse(result.begin(), result.end());
return result;
}
};
namespace internal {
template <class T>
class DijkstraHeap {
private:
const std::vector<T>& dist_;
std::vector<int> heap_;
std::vector<int> position_;
bool less(int first, int second) const {
return dist_[heap_[first]] < dist_[heap_[second]];
}
void swap_nodes(int first, int second) {
std::swap(heap_[first], heap_[second]);
position_[heap_[first]] = first;
position_[heap_[second]] = second;
}
void sift_up(int index) {
while (index != 0) {
const int parent = (index - 1) / 2;
if (!less(index, parent)) break;
swap_nodes(index, parent);
index = parent;
}
}
void sift_down(int index) {
while (2 * index + 1 < int(heap_.size())) {
int child = 2 * index + 1;
if (child + 1 < int(heap_.size()) && less(child + 1, child)) {
++child;
}
if (!less(child, index)) break;
swap_nodes(index, child);
index = child;
}
}
public:
DijkstraHeap(const std::vector<T>& dist, int size)
: dist_(dist), position_(size, -1) {
heap_.reserve(size);
}
bool empty() const {
return heap_.empty();
}
void push_or_decrease(int vertex) {
int& position = position_[vertex];
if (position == -1) {
position = int(heap_.size());
heap_.push_back(vertex);
}
sift_up(position);
}
int pop_min() {
const int result = heap_.front();
position_[result] = -1;
if (heap_.size() == 1) {
heap_.pop_back();
return result;
}
heap_.front() = heap_.back();
position_[heap_.front()] = 0;
heap_.pop_back();
sift_down(0);
return result;
}
};
} // namespace internal
template <class T>
DijkstraResult<T> dijkstra(const Graph<T>& g,
const std::vector<int>& sources) {
int n = g.size();
DijkstraResult<T> result;
result.dist.resize(n);
result.reached.assign(n, false);
result.parent.assign(n, -1);
result.parent_edge.assign(n, -1);
internal::DijkstraHeap<T> que(result.dist, n);
for (int s : sources) {
assert(0 <= s && s < n);
if (result.reached[s]) continue;
result.reached[s] = true;
result.dist[s] = T();
que.push_or_decrease(s);
}
while (!que.empty()) {
const int current = que.pop_min();
for (const auto& e : g[current]) {
if (!e.alive) continue;
T nd = result.dist[current] + e.cost;
if (result.reached[e.to] && !(nd < result.dist[e.to])) continue;
result.reached[e.to] = true;
result.dist[e.to] = std::move(nd);
result.parent[e.to] = current;
result.parent_edge[e.to] = e.id;
que.push_or_decrease(e.to);
}
}
return result;
}
template <class T>
DijkstraResult<T> dijkstra(const Graph<T>& g, int s) {
return dijkstra(g, std::vector<int>{s});
}
// Compatibility overload: unreachable distances are replaced by inf after the
// search. Reachability itself never depends on this sentinel.
template <class T>
DijkstraResult<T> dijkstra(const Graph<T>& g,
const std::vector<int>& sources, const T& inf) {
DijkstraResult<T> result = dijkstra(g, sources);
result.inf = inf;
for (int v = 0; v < int(result.dist.size()); v++) {
if (!result.reachable(v)) result.dist[v] = inf;
}
return result;
}
template <class T>
DijkstraResult<T> dijkstra(const Graph<T>& g, int s, const T& inf) {
return dijkstra(g, std::vector<int>{s}, inf);
}
} // namespace graph
} // namespace m1une
#line 9 "verify/graph/dijkstra_custom_cost.test.cpp"
struct Cost {
long long value = 0;
Cost operator+(const Cost& other) const {
return Cost{value + other.value};
}
friend bool operator<(const Cost& first, const Cost& second) {
return first.value < second.value;
}
};
void test_custom_cost() {
m1une::graph::Graph<Cost> graph(6);
graph.add_directed_edge(0, 1, Cost{8});
graph.add_directed_edge(0, 2, Cost{2});
graph.add_directed_edge(2, 1, Cost{3});
graph.add_directed_edge(1, 3, Cost{4});
graph.add_directed_edge(2, 3, Cost{20});
graph.add_directed_edge(4, 3, Cost{1});
auto result = m1une::graph::dijkstra(graph, 0);
assert(result.reachable(0));
assert(result.reachable(3));
assert(!result.reachable(4));
assert(!result.reachable(5));
assert(result.dist[0].value == 0);
assert(result.dist[1].value == 5);
assert(result.dist[3].value == 9);
assert((result.path(3) == std::vector<int>{0, 2, 1, 3}));
auto multi = m1une::graph::dijkstra(
graph, std::vector<int>{0, 4, 0});
assert(multi.reachable(4));
assert(multi.dist[3].value == 1);
assert((multi.path(3) == std::vector<int>{4, 3}));
}
void test_explicit_sentinel_is_not_reachability() {
m1une::graph::Graph<Cost> graph(3);
graph.add_directed_edge(0, 1, Cost{99});
auto result = m1une::graph::dijkstra(graph, 0, Cost{99});
assert(result.inf.value == 99);
assert(result.reachable(1));
assert(result.dist[1].value == 99);
assert(!result.reachable(2));
assert(result.dist[2].value == 99);
}
int main() {
test_custom_cost();
test_explicit_sentinel_is_not_reachability();
long long a, b;
std::cin >> a >> b;
std::cout << a + b << '\n';
}
verify/graph/dijkstra_custom_cost.test.cpp