ABC481 F - Evil Shortest Path
頂点 辺の有向グラフがあり、各辺には 以上 以下の数字が書かれています。通った辺の数字を順につなげた整数をその移動のスコアとします。 のそれぞれについて、頂点 から頂点 へ移動するときのスコアの最小値を で割ったあまりを求める問題です。
同じ頂点や辺を何度通ってもよく、頂点 から全頂点に到達できることが保証されます(、)。
最小のスコアを与える移動
Section titled “最小のスコアを与える移動”辺の数字はどれも 以上なので、スコアの桁数は通った辺の本数に等しく、桁数が少ないほどスコアは小さくなります。よって、スコアが最小になる移動は、頂点 からの最短路(辺の本数が最小の移動)のどれかです。桁数が同じ整数どうしの大小は、数字の列の辞書順と一致するので、最短路のうち数字の列が辞書順で最小のものを求めればよいです。
頂点 からの最短距離 を BFS で求めます。最短路で使える辺は、 を満たす辺 だけです。頂点 への辞書順最小の列を とすると、
です。長さの同じ列どうしでは、 より大きい列の後ろに数字をつなげても、 の後ろにつなげた列より小さくはならないからです。 の小さい順に頂点を見ていけば、 を使うときには が確定しています。
Trie で列を持つ
Section titled “Trie で列を持つ”列 の長さは最大で になるので、すべての列をそのまま持つと間に合いません。そこで、列を Trie のノードで表します。 のノードから辺の数字で 1 文字進んだノードが「 の後ろに数字をつなげた列」です。1 本の辺でノードは高々 1 個しか増えないので、ノードは 個以下です。
2 つのノードの列の辞書順の比較は、2 つのノードの最小共通祖先(LCA)のすぐ下の文字を比べればできます。ノードごとに祖先への飛び先を持っておけば、LCA は で求まります。
答えのあまりは、 を更新するたびに として一緒に更新します。計算量は です。
なお、Trie を使わなくても、同じ距離の頂点どうしの の順位を距離ごとに求めておき、「 の順位、辺の数字」の組をソートして次の距離の順位を決める方法でも解けます。
別解:スコアを距離にしてダイクストラ法
Section titled “別解:スコアを距離にしてダイクストラ法”スコアを「数字の列の長さで比べ、長さが同じなら辞書順で比べる」値と考えると、この問題はスコアを距離とする最短路問題です。この距離には次の 2 つの性質があります。
- 辺をたどると、列が 1 文字長くなるので、距離は必ず大きくなる。
- 列 が列 より小さければ、同じ数字をつなげた後も、 のほうが 以下になる。
この 2 つが成り立つので、ダイクストラ法がそのまま使えます。距離は上と同じく Trie のノードで持ち、比較 1 回が なので、全体の計算量は です。BFS の層ごとに処理する工夫を、ダイクストラ法に任せる形になります。
C++(BFS)
#include "shogo-library/base/all"#include "shogo-library/graph/shortest-path.hpp"#include "shogo-library/math/modint.hpp"#include "shogo-library/string/trie.hpp"#include "shogo-library/utility/vector_func.hpp"using mint = modint998244353;
void solve() { LL(N, M); Graph<> g(N); g.read(M, -1, true, true); auto d = shortest_path(g, 0, false).dist; Trie<9, 1> trie; vl node(N, -1); vec<mint> ans(N); node[0] = 0; for (ll u : sorted_idx(d)) { for (auto &e : g[u]) { if (d[e.dst] != d[u] + 1) continue; ll v = trie.extend(node[u], e.cost); if (node[e.dst] == -1 || trie.less(v, node[e.dst])) { node[e.dst] = v; ans[e.dst] = ans[u] * 10 + e.cost; } } } rep(v, 1, N) print(ans[v]);}
int main() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); solve();}g.read(M, -1, true, true) は、辺の数字を重みとして、有向辺を 本読みます。shortest_path(g, 0, false) の第 3 引数 false は重みを無視することを表し、BFS で辺の本数の最短距離を求めます。
Trie<9, 1> は、文字 から を使う Trie です。根(ノード )が空の列で、頂点 の列に対応します。node[v] は のノード、ans[v] はそのあまりです。
sorted_idx(d) は d の小さい順に並べた頂点の番号の列です。trie.extend(node[u], e.cost) で の後ろに辺の数字をつなげた列のノードを(なければ作って)求め、trie.less(v, node[e.dst]) で、いまの より辞書順で小さいかを で比べています。
使用ライブラリ:cpp_include@4b58304
C++(ダイクストラ法)
#include "shogo-library/base/all"#include "shogo-library/graph/shortest-path.hpp"#include "shogo-library/math/modint.hpp"#include "shogo-library/string/trie.hpp"using mint = modint998244353;
Trie<9, 1> trie;
struct Score { ll node = 0; ll digit = 0; mint val = 0; Score() = default; Score(ll digit) : digit(digit) {} static Score inf() { Score res; res.node = -1; return res; } friend Score operator+(const Score &a, const Score &e) { Score res; res.node = trie.extend(a.node, e.digit); res.val = a.val * 10 + e.digit; return res; } friend bool operator<(const Score &a, const Score &b) { if (a.node == -1) return false; if (b.node == -1) return true; if (trie.depth(a.node) != trie.depth(b.node)) return trie.depth(a.node) < trie.depth(b.node); return trie.less(a.node, b.node); } friend bool operator>(const Score &a, const Score &b) { return b < a; } friend bool operator==(const Score &a, const Score &b) { return a.node == b.node; } friend std::istream &operator>>(std::istream &is, Score &s) { return is >> s.digit; }};
void solve() { LL(N, M); Graph<Score> g(N); g.read(M, -1, true, true); auto d = shortest_path(g, 0, true, Score::inf()).dist; rep(v, 1, N) print(d[v].val);}
int main() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); solve();}Score は距離と辺のコストの両方に使う型です。距離としては、node がスコアの列の Trie のノード、val がそのあまりです。辺のコストとしては、digit に辺の数字を入れます。
operator+は、距離に辺のコストを足す操作で、Trie を辺の数字で 1 文字進めます。operator<は、列の長さ(Trie の深さ)で比べ、同じならtrie.lessで辞書順に比べます。node == -1は到達できないことを表す最大の値inf()です。operator>とoperator==は、ライブラリのダイクストラ法の中で、距離の比較と未到達の判定(infとの比較)に使われます。shortest_pathのinfの既定値はstd::numeric_limits<Cost>::max() / 4で、この型では使えないので、Score::inf()を渡しています。g.readは、重みをCost c(1)で作ってからstd::cin >> cで読むので、整数からのコンストラクタとoperator>>を用意しています。始点の距離0はScore(0)で、Trie の根(空の列)になります。
使用ライブラリ:cpp_include@4b58304