cp-library
競技プログラミング用 C++ ライブラリ
Dijkstra の一意経路の探索
components/dijkstra_unique.hpp · GitHub で見る
共通ページ
Dijkstra が内部で使う、各頂点の入次数が高々 1 の場合の探索です。通常は graph/dijkstra.hpp を include し、CSR に対して dijkstra_path(g,start,target) を呼びます。条件の判定と使い分けは自動で行います。
各頂点へ入る辺が高々 1 本なら、始点から各頂点へ向かう単純経路も高々 1 本です。距離の大小による取り出し順を決める必要がないため、優先度付きキューを省けます。出辺が 1 本の区間は直接たどり、分岐した先だけを配列へ保存します。
| 操作 | 内容・返り値 | 計算量 |
|---|---|---|
shortest_path_detail::unique_path(g,start,target,inf,parent) |
最短距離と始点・終点を含む頂点列を返す。到達不能は {T(-1), {}}
|
\(O(n+m)\) |
内部関数の g は size() と g[v] を持ち、g[v] は empty()・size()・添字アクセスが使える {行き先, 重み} の範囲を返すものとします。辺への参照は探索中に有効である必要があります。全頂点の入次数は高々 1、重みは非負、start != target、inf は正とします。parent は長さ \(n\) の配列を渡します。公開関数は必要な準備を行います。
始点に戻る辺を省けば、同じ頂点へ 2 回進むことはありません。始点以外で閉路へ合流するには、その頂点の入次数が 2 以上必要になるためです。目的地を最初に見つけた時点で経路が確定します。経路上の重みは始点からの順に加算し、inf 以上になる部分は探索しません。
頂点数を \(n\)、辺数を \(m\) として \(O(n+m)\) 時間・追加空間です。要素の演算・比較・コピーを \(O(1)\) とします。
依存ライブラリ
検証コード
コード
#ifndef DIJKSTRA_UNIQUE_HPP
#define DIJKSTRA_UNIQUE_HPP
#include "dijkstra_queue.hpp"
#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>
namespace shortest_path_detail {
template<class G, class T>
std::pair<T, std::vector<int>> unique_path(const G &g, int st, int target, T inf, std::vector<int> &parent) {
using State = std::pair<T, int>;
std::vector<State> pending;
pending.emplace_back(T(0), st);
while (!pending.empty()) {
auto [cost, v] = std::move(pending.back());
pending.pop_back();
for (const auto &first : g[v]) {
const auto *edge = &first;
int from = v;
T prefix = cost;
for (;;) {
const auto &[to, weight] = *edge;
assert(weight >= 0);
if (to == st) break;
if (reaches_limit(weight, T(inf - prefix))) break;
T next = prefix + weight;
if (to == target) {
std::vector<int> path{to};
for (int u = from; u != st; u = parent[u]) path.push_back(u);
path.push_back(st);
std::reverse(path.begin(), path.end());
return {std::move(next), std::move(path)};
}
const auto &outgoing = g[to];
if (outgoing.empty()) break;
parent[to] = from;
if (outgoing.size() != 1) {
pending.emplace_back(std::move(next), to);
break;
}
from = to;
edge = &outgoing[0];
prefix = std::move(next);
}
}
}
return {T(-1), {}};
}
}
#endif
#line 1 "components/dijkstra_unique.hpp"
#line 1 "components/dijkstra_queue.hpp"
#line 1 "components/RadixHeap.hpp"
#include <algorithm>
#include <bit>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <type_traits>
#include <utility>
#include <vector>
template <class Key = std::uint64_t, class T = int>
class RadixHeap {
static_assert(std::is_integral_v<Key> && !std::is_same_v<Key, bool> && sizeof(Key) <= 8);
using U = std::make_unsigned_t<Key>;
using State = std::pair<Key, T>;
std::vector<State> bucket[std::numeric_limits<U>::digits + 1];
Key lower;
std::size_t count = 0;
int index(Key key) const { return std::bit_width(U(U(key) ^ U(lower))); }
void refill() {
assert(count);
if (!bucket[0].empty()) return;
int i = 1;
while (bucket[i].empty()) ++i;
lower = bucket[i][0].first;
for (const auto &s : bucket[i]) lower = std::min(lower, s.first);
for (auto &s : bucket[i]) bucket[index(s.first)].push_back(std::move(s));
bucket[i].clear();
}
public:
explicit RadixHeap(Key minimum = 0) : lower(minimum) {}
RadixHeap(const RadixHeap &) = default;
RadixHeap &operator=(const RadixHeap &) = default;
RadixHeap(RadixHeap &&other) noexcept : lower(other.lower), count(std::exchange(other.count, 0)) {
for (int i = 0; i <= std::numeric_limits<U>::digits; ++i) bucket[i] = std::move(other.bucket[i]);
}
RadixHeap &operator=(RadixHeap &&other) noexcept {
if (this != &other) {
lower = other.lower;
count = std::exchange(other.count, 0);
for (int i = 0; i <= std::numeric_limits<U>::digits; ++i) bucket[i] = std::move(other.bucket[i]);
}
return *this;
}
bool empty() const { return count == 0; }
std::size_t size() const { return count; }
Key last() const { return lower; }
void clear(Key minimum = 0) {
for (auto &b : bucket) b.clear();
lower = minimum;
count = 0;
}
void push(State s) {
assert(s.first >= lower);
bucket[index(s.first)].push_back(std::move(s));
++count;
}
const State &top() {
refill();
return bucket[0].back();
}
void pop() {
refill();
bucket[0].pop_back();
--count;
}
State pop_value() {
refill();
State s = std::move(bucket[0].back());
bucket[0].pop_back();
--count;
return s;
}
};
#line 10 "components/dijkstra_queue.hpp"
#include <functional>
#line 15 "components/dijkstra_queue.hpp"
namespace shortest_path_detail {
template<class Weight, class Distance>
bool reaches_limit(const Weight &weight, const Distance &limit) {
if constexpr (std::numeric_limits<Weight>::is_integer && std::numeric_limits<Weight>::is_bounded &&
std::numeric_limits<Distance>::is_integer && std::numeric_limits<Distance>::is_bounded) {
using Compare = std::common_type_t<Weight, Distance>;
return Compare(weight) >= Compare(limit);
} else return weight >= limit;
}
template<class T> class RadixQueue {
static_assert(std::is_integral_v<T> && sizeof(T) <= 8);
struct State { T key; int vertex; };
State small_[32];
std::vector<std::uint64_t> buckets_[33];
std::uint32_t minimum_[33];
std::uint32_t occupied_ = 0;
std::uint64_t last_ = 0;
std::size_t count_ = 0;
int mode_ = 0;
RadixHeap<std::uint64_t> wide_;
void put(std::uint64_t state) {
std::uint32_t key = state >> 32;
int index = std::bit_width(key ^ std::uint32_t(last_));
buckets_[index].push_back(state);
if (index) {
occupied_ |= std::uint32_t(1) << (index - 1);
minimum_[index] = std::min(minimum_[index], key);
}
}
void promote() {
if (mode_ == 0) {
for (std::size_t i = 0; i < count_; ++i) wide_.push({std::uint64_t(small_[i].key), small_[i].vertex});
} else {
for (auto &bucket : buckets_) {
for (auto state : bucket) {
std::uint64_t key = last_ + std::uint32_t(std::uint32_t(state >> 32) - std::uint32_t(last_));
wide_.push({key, int(std::uint32_t(state))});
}
bucket.clear();
}
}
mode_ = 2;
}
public:
bool empty() const { return count_ == 0; }
void push(T key, int vertex) {
assert(key >= 0 && std::uint64_t(key) >= last_);
if (mode_ == 0 && count_ < 32) {
small_[count_++] = {key, vertex};
return;
}
if (mode_ == 0) {
bool narrow = std::uint64_t(key) - last_ <= std::uint64_t(std::numeric_limits<std::int32_t>::max());
for (std::size_t i = 0; i < count_; ++i)
narrow &= std::uint64_t(small_[i].key) - last_ <= std::uint64_t(std::numeric_limits<std::int32_t>::max());
if (narrow) {
std::fill_n(minimum_, 33, std::numeric_limits<std::uint32_t>::max());
for (std::size_t i = 0; i < count_; ++i)
put((std::uint64_t(std::uint32_t(small_[i].key)) << 32) | std::uint32_t(small_[i].vertex));
mode_ = 1;
} else promote();
}
if (mode_ == 1 && std::uint64_t(key) - last_ > std::uint64_t(std::numeric_limits<std::int32_t>::max())) promote();
if (mode_ == 2) wide_.push({std::uint64_t(key), vertex});
else put((std::uint64_t(std::uint32_t(key)) << 32) | std::uint32_t(vertex));
++count_;
}
std::pair<T, int> pop() {
assert(count_);
if (mode_ == 0) {
std::size_t best = 0;
for (std::size_t i = 1; i < count_; ++i)
if (small_[i].key < small_[best].key) best = i;
State state = small_[best];
small_[best] = small_[--count_];
last_ = std::uint64_t(state.key);
return {state.key, state.vertex};
}
if (mode_ == 2) {
auto state = wide_.pop_value();
last_ = state.first;
--count_;
return {T(state.first), state.second};
}
if (buckets_[0].empty()) {
int index = std::countr_zero(occupied_) + 1;
last_ += std::uint32_t(minimum_[index] - std::uint32_t(last_));
minimum_[index] = std::numeric_limits<std::uint32_t>::max();
occupied_ &= occupied_ - 1;
if (buckets_[index].size() == 1) {
auto state = buckets_[index].back();
buckets_[index].clear();
--count_;
return {T(last_), int(std::uint32_t(state))};
}
for (auto state : buckets_[index]) put(state);
buckets_[index].clear();
}
auto state = buckets_[0].back();
buckets_[0].pop_back();
--count_;
return {T(last_), int(std::uint32_t(state))};
}
};
template<class T> class BinaryQueue {
using State = std::pair<T, int>;
std::vector<State> heap_;
public:
bool empty() const { return heap_.empty(); }
void push(T cost, int vertex) {
heap_.emplace_back(std::move(cost), vertex);
std::push_heap(heap_.begin(), heap_.end(), std::greater<State>());
}
State pop() {
std::pop_heap(heap_.begin(), heap_.end(), std::greater<State>());
State state = std::move(heap_.back());
heap_.pop_back();
return state;
}
};
template<class T>
using DistanceQueue = std::conditional_t<std::is_integral_v<T> && sizeof(T) <= 8, RadixQueue<T>, BinaryQueue<T>>;
}
#line 9 "components/dijkstra_unique.hpp"
namespace shortest_path_detail {
template<class G, class T>
std::pair<T, std::vector<int>> unique_path(const G &g, int st, int target, T inf, std::vector<int> &parent) {
using State = std::pair<T, int>;
std::vector<State> pending;
pending.emplace_back(T(0), st);
while (!pending.empty()) {
auto [cost, v] = std::move(pending.back());
pending.pop_back();
for (const auto &first : g[v]) {
const auto *edge = &first;
int from = v;
T prefix = cost;
for (;;) {
const auto &[to, weight] = *edge;
assert(weight >= 0);
if (to == st) break;
if (reaches_limit(weight, T(inf - prefix))) break;
T next = prefix + weight;
if (to == target) {
std::vector<int> path{to};
for (int u = from; u != st; u = parent[u]) path.push_back(u);
path.push_back(st);
std::reverse(path.begin(), path.end());
return {std::move(next), std::move(path)};
}
const auto &outgoing = g[to];
if (outgoing.empty()) break;
parent[to] = from;
if (outgoing.size() != 1) {
pending.emplace_back(std::move(next), to);
break;
}
from = to;
edge = &outgoing[0];
prefix = std::move(next);
}
}
}
return {T(-1), {}};
}
}