這場比賽沒打，看同學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; }

轉載于:https://www.cnblogs.com/daklqw/p/11546379.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的1209F - Koala and Notebook的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。