N N N 頂点 M M M 辺の有向グラフがあり、各辺には 1 1 1 以上 9 9 9 以下の数字が書かれています。通った辺の数字を順につなげた整数をその移動のスコアとします。v = 2 , 3 , … , N v = 2, 3, \ldots, N v = 2 , 3 , … , N のそれぞれについて、頂点 1 1 1 から頂点 v v v へ移動するときのスコアの最小値を 998244353 998244353 998244353 で割ったあまりを求める問題です。
同じ頂点や辺を何度通ってもよく、頂点 1 1 1 から全頂点に到達できることが保証されます(2 ≤ N ≤ 2 × 10 5 2 \le N \le 2 \times 10^5 2 ≤ N ≤ 2 × 1 0 5 、N − 1 ≤ M ≤ 2 × 10 5 N - 1 \le M \le 2 \times 10^5 N − 1 ≤ M ≤ 2 × 1 0 5 )。
辺の数字はどれも 1 1 1 以上なので、スコアの桁数は通った辺の本数に等しく、桁数が少ないほどスコアは小さくなります。よって、スコアが最小になる移動は、頂点 1 1 1 からの最短路(辺の本数が最小の移動)のどれかです。桁数が同じ整数どうしの大小は、数字の列の辞書順と一致するので、最短路のうち数字の列が辞書順で最小のものを求めればよいです。
頂点 1 1 1 からの最短距離 d d d を BFS で求めます。最短路で使える辺は、d v = d u + 1 d_v = d_u + 1 d v = d u + 1 を満たす辺 u → v u \to v u → v だけです。頂点 v v v への辞書順最小の列を s v s_v s v とすると、
s v = min u → v , d v = d u + 1 ( s u の後ろに辺の数字をつなげた列 ) s_v = \min_{u \to v,\ d_v = d_u + 1} (s_u \text{ の後ろに辺の数字をつなげた列}) s v = u → v , d v = d u + 1 min ( s u の後ろに辺の数字をつなげた列 )
です。長さの同じ列どうしでは、s u s_u s u より大きい列の後ろに数字をつなげても、s u s_u s u の後ろにつなげた列より小さくはならないからです。d d d の小さい順に頂点を見ていけば、s u s_u s u を使うときには s u s_u s u が確定しています。
列 s v s_v s v の長さは最大で N − 1 N - 1 N − 1 になるので、すべての列をそのまま持つと間に合いません。そこで、列を Trie のノードで表します。s u s_u s u のノードから辺の数字で 1 文字進んだノードが「s u s_u s u の後ろに数字をつなげた列」です。1 本の辺でノードは高々 1 個しか増えないので、ノードは M + 1 M + 1 M + 1 個以下です。
2 つのノードの列の辞書順の比較は、2 つのノードの最小共通祖先(LCA)のすぐ下の文字を比べればできます。ノードごとに祖先への飛び先を持っておけば、LCA は O ( log N ) O(\log N) O ( log N ) で求まります。
答えのあまりは、s v s_v s v を更新するたびに ( s u のあまり ) × 10 + ( 数字 ) (s_u \text{ のあまり}) \times 10 + (\text{数字}) ( s u のあまり ) × 10 + ( 数字 ) として一緒に更新します。計算量は O ( ( N + M ) log N ) O((N + M) \log N) O (( N + M ) log N ) です。
なお、Trie を使わなくても、同じ距離の頂点どうしの s v s_v s v の順位を距離ごとに求めておき、「s u s_u s u の順位、辺の数字」の組をソートして次の距離の順位を決める方法でも解けます。
スコアを「数字の列の長さで比べ、長さが同じなら辞書順で比べる」値と考えると、この問題はスコアを距離とする最短路問題です。この距離には次の 2 つの性質があります。
辺をたどると、列が 1 文字長くなるので、距離は必ず大きくなる。
列 a a a が列 b b b より小さければ、同じ数字をつなげた後も、a a a のほうが b b b 以下になる。
この 2 つが成り立つので、ダイクストラ法 がそのまま使えます。距離は上と同じく Trie のノードで持ち、比較 1 回が O ( log N ) O(\log N) O ( log N ) なので、全体の計算量は O ( M log M log N ) O(M \log M \log N) O ( M log M log N ) です。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;
g . read ( M , - 1 , true , true );
auto d = shortest_path ( g , 0 , false ). dist ;
for (ll u : sorted_idx ( d )) {
if ( d [ e . dst ] != d [ u ] + 1 )
ll v = trie . extend ( node [ u ], e . cost );
if ( node [ e . dst ] == - 1 || trie . less ( v , node [ e . dst ])) {
ans [ e . dst ] = ans [ u ] * 10 + e . cost ;
rep ( v , 1 , N ) print ( ans [ v ]);
std::ios_base:: sync_with_stdio ( false );
g.read(M, -1, true, true) は、辺の数字を重みとして、有向辺を M M M 本読みます。shortest_path(g, 0, false) の第 3 引数 false は重みを無視することを表し、BFS で辺の本数の最短距離を求めます。
Trie<9, 1> は、文字 1 1 1 から 9 9 9 を使う Trie です。根(ノード 0 0 0 )が空の列で、頂点 1 1 1 の列に対応します。node[v] は s v s_v s v のノード、ans[v] はそのあまりです。
sorted_idx(d) は d の小さい順に並べた頂点の番号の列です。trie.extend(node[u], e.cost) で s u s_u s u の後ろに辺の数字をつなげた列のノードを(なければ作って)求め、trie.less(v, node[e.dst]) で、いまの s v s_v s v より辞書順で小さいかを O ( log N ) O(\log N) O ( log N ) で比べています。
使用ライブラリ: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;
Score (ll digit ) : digit ( digit ) {}
friend Score operator +( const Score & a , const Score & e ) {
res . node = trie . extend ( a . node , e . digit );
res . val = a . val * 10 + e . digit ;
friend bool operator <( const Score & a , const Score & b ) {
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 ; }
g . read ( M , - 1 , true , true );
auto d = shortest_path ( g , 0 , true , Score:: inf ()). dist ;
rep ( v , 1 , N ) print ( d [ v ]. val );
std::ios_base:: sync_with_stdio ( false );
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