CF-1209 F. Koala and Notebook(建图BFS)

CF-1209 F. Koala and Notebook(建图BFS)

题目链接

题意

n个城市m个双向边,从点1可以到达任何点,把点1到到其他点所经过的边写成一行可以得到一个大数,你的任务使得这个数字尽可能的小.

思路

例如第i条边是u->v,把这条边拆成u->i_1->i_2->…->i_n->v

然后bfs:对于相同状态的点依次从小数[0-9]扩展,扩展到的点更新答案

#include <bits/stdc++.h> const int maxn = 1e6 + 5; const int mod = 1e9 + 7; using namespace std; vector<int> g[maxn][10], que[maxn]; int cnt, vis[maxn]; long long ans[maxn]; void add(int u, int v, int d) {vector<int> tmp;while (d) {tmp.push_back(d%10);d /= 10;}reverse(tmp.begin(), tmp.end());int l = u, r, len = tmp.size();for (int i = 0; i < len; ++i) {if (i == len-1) r = v;else r = ++cnt;g[l][tmp[i]].push_back(r);l = r;}// 反向l = v;for (int i = 0; i < len; ++i) {if (i == len-1) r = u;else r = ++cnt;g[l][tmp[i]].push_back(r);l = r; } } int main() {int n, m;cin >> n >> m;cnt = n;for (int i = 1; i <= m; ++i) {int u, v;cin >> u >> v;add(u, v, i);}que[1].push_back(1);vis[1] = 1;int now = 1;for (int k = 1; k <= now; ++k){for (int i = 0; i < 10; ++i) { // small is firstint flag = 0;for (auto u : que[k]) {for (auto v : g[u][i]) {if (vis[v]) continue;vis[v] = flag = 1;ans[v] = (ans[u]*10 + i) % mod;que[now+1].push_back(v);}}if (flag) now++;}}for (int i = 2; i <= n; ++i) {cout << ans[i] << endl;}return 0; } 与50位技术专家面对面20年技术见证，附赠技术全景图

总结

以上是生活随笔为你收集整理的CF-1209 F. Koala and Notebook(建图BFS)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。