@codeforces - 1209F@ Koala and Notebook

素颜马尾好姑娘i 2023-06-01 12:58 15阅读 0赞

*  @description@
 *  @solution@
 *  @accepted code@
 *  @details@

--------------------

## @description@ ##

给定一个 n 点 m 边的无向连通图，每条边的编号按照输入顺序依次为 1, 2, ..., m。  
现从 1 号点出发，当经过编号为 i 的边时，将 i 写下来。因为写的数之间没有空隙，所以写下来的所有数最终会连成一个数。  
对于每一个除 1 以外的点，当它作为终点时，最终连成的数最小是多少？  
输出答案模 10^9 + 7。注意，你应该输出 **最小可能的数的余数**，而不应该是 **最小可能的余数**。

**Input**  
第一行包含两个整数 n 和 m (2≤n≤10^5,n−1≤m≤10^5)，表示点数与边数。  
接下来 m 行，每行两个整数 xi 与 yi，表示第 i 条无向边连接 xi, yi。  
保证没有重边。保证图连通。

**Output**  
输出 n - 1 个数字，第 i 个数字表示以 i + 1 为终点的最小可能的数 mod 10^9 + 7。

**Examples**  
**Input**  
11 10  
1 2  
2 3  
3 4  
4 5  
5 6  
6 7  
7 8  
8 9  
9 10  
10 11  
**Output**  
1  
12  
123  
1234  
12345  
123456  
1234567  
12345678  
123456789  
345678826

## @solution@ ##

首先考虑一条边 u -> v 的权值如果为多位数 i，它的十进制表达为 \\((d1...dm)\_10\\)，则可以拆成 m 条边 u -> a1(d1), a1 -> a2(d2), ..., am-1 -> v(dm)。  
这样就可以把每条边的权值都变为 0~9，方便我们下面的操作。

两个十进制数的比较，先比较位数，位数相同再比较字典序。  
而在我们拆边后的图中，一条路径的距离就表示了这条路径代表的数的位数。  
我们可以从点 1 出发跑最短路（其实跑 bfs 就好了），构建最短路图，则顺着最短路图走就可以保证位数最优。

接下来在最短路图上，我们考虑怎么才能走字典序最小的路径。  
字典序是从前比到后，所以我们肯定是尽量保证先走权值最小的边。

但是有一个问题：假如权值最小的边有多个，应该选哪个？  
正确的方法应该是同时增广这些边。将这些边连接的点连成链表形式，然后 dfs 的时候传表头即可。

## @accepted code@ ##

#include<queue> #include<cstdio> #include<algorithm> using namespace std; const int MAXN = 2000000; const int MOD = int(1E9) + 7; struct edge{ int to, key; edge(int _t=0, int _k=0):to(_t), key(_k) {} }; vector<edge>G[MAXN + 5]; void addedge(int u, int v, int w) { G[u].push_back(edge(v, w)); // printf("! %d %d %d\n", u, v, w); } int cnt; void func(int u, int v, int id) { int p = id; while( p ) { if( p >= 10 ) addedge(++cnt, u, p % 10), u = cnt; else addedge(v, u, p % 10); p /= 10; } } int d[MAXN + 5], n, m; void bfs(int x) { queue<int>que; que.push(x); d[x] = 1; while( !que.empty() ) { int f = que.front(); que.pop(); for(int i=0;i<G[f].size();i++) { edge p = G[f][i]; if( !d[p.to] ) { d[p.to] = d[f] + 1; que.push(p.to); } } } } int ans[MAXN + 5], nxt[MAXN + 5]; bool vis[MAXN + 5]; void dfs(int x, int k) { int p = x; while( p ) ans[p] = k, p = nxt[p]; for(int i=0;i<10;i++) { int q = -1, fir = -1; p = x; while( p ) { for(int j=0;j<G[p].size();j++) { edge &r = G[p][j]; if( vis[r.to] || d[p] + 1 != d[r.to] ) continue; if( r.key == i ) { if( q != -1 ) nxt[q] = r.to; else fir = r.to; vis[q = r.to] = true; } } p = nxt[p]; } if( fir != -1 ) dfs(fir, (10LL*k + i)%MOD); } } int main() { scanf("%d%d", &n, &m), cnt = n; for(int i=1;i<=m;i++) { int x, y; scanf("%d%d", &x, &y); func(x, y, i), func(y, x, i); } bfs(1), vis[1] = true, dfs(1, 0); for(int i=2;i<=n;i++) printf("%d\n", ans[i]); }

## @details@ ##

注意原图虽然是无向边，但是我们拆出来的边就变成了有向边。

枚举最小权值边，可以通过枚举 0~9（即枚举边权），找出对应权值的边。

转载于:https://www.cnblogs.com/Tiw-Air-OAO/p/11521294.html