这场比赛没打，看同学fst了，于是来看看。
这道题看似简单，但是没想清楚细节真的不太行。像现在熬到十一点左右，脑子真的不行。
首先显然位数越小越好，因为每一位要比较，不如拆点。此时要拆成两条有向链（开始实现成了无向链）
然后这个时候就可以很方便地跑最短路了。但是细节比较多。
首先直接贪心走最小边然后bfs是不行的，所以要考虑分层（这里也挂了）。对于每一个点伸出去边长相等的属于一个等价类。此时容易证明等价类数量是 \(O(m)\) 的。
于是直接分层跑即可。由字典序从小到大枚举等价类，易知更新时不断在等价类列表尾插入一个新的点是对的。
这道题就这两个难点，于是作为低水平选手两处都被坑到了。
#include <bits/stdc++.h>
const int mod = 1000000007;
const int MAXN = 1100010;
std::vector<int> G[MAXN][10], qs[MAXN];
void addedge(int b, int e, int v) {
G[b][v].push_back(e);
}
int n, m, idx, dp[MAXN];
bool vis[MAXN];
int main() {
std::ios_base::sync_with_stdio(false), std::cin.tie(0);
std::cin >> n >> m; idx = n;
for (int i = 1; i <= m; ++i) {
int t1, t2; std::cin >> t1 >> t2;
static int arr[10], bak; bak = 0;
int t = i;
while (t) arr[bak++] = t % 10, t /= 10;
int lst = t1;
for (int j = bak - 1; ~j; --j) {
int now = j ? ++idx : t2;
addedge(lst, now, arr[j]);
lst = now;
}
for (int j = bak - 1; ~j; --j) {
int now = j ? ++idx : t1;
addedge(lst, now, arr[j]);
lst = now;
}
}
int T;
qs[T = 1].push_back(1); vis[1] = true;
for (int P = 1; P <= T; ++P) {
for (int j = 0; j != 10; ++j) {
bool flg = false;
for (auto t : qs[P]) {
for (auto v : G[t][j]) {
if (vis[v]) continue;
vis[v] = true;
dp[v] = (dp[t] * 10ll + j) % mod;
qs[T + 1].push_back(v);
flg = true;
}
}
if (flg) ++T;
}
}
for (int i = 2; i <= n; ++i)
std::cout << dp[i] << '\n';
return 0;
}