题目描述
小明有一幅地图，这幅地图上标注了$n$个城市，$m$条双向道路。
第$i$条道路的编号是$i$。
小明沿着城市$1$，向其他城市走去，在走的过程中，顺手把经过的道路的编号标注了出来。
例如：他通过编号为$33,35,446$的边从$1$号城市出发，经过城市$2,5$到达了$9$号城市，那么他就标注了一串形如$3335446$的数字（因为没有空格，所以数字连到了一起）。
问：小明从$1$号城市到达每一个点，所标注出来的数字最小是多少？由于答案有点大，所以只需要输出答案$mod$ $10^9+7$即可。
输入格式
第一行两个数字$n,m$，如题所述。
接下来$m$行，第$i$行两个正整数$u,v$，表示编号为$i$的边两边的城市编号。
输出格式
输出$n-1$个数字，表示从起点$1$到达每一个城市的最小答案。
样例输入1
11 10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11样例输出1
1
12
123
1234
12345
123456
1234567
12345678
123456789
345678826样例输入2
12 19
1 2
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
3 11
11 12
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10样例输出2
1
12
13
14
15
16
17
18
19
1210
121011数据范围
对于10%的数据：$n≤10,m≤20$。（下发样例1）
对于30%的数据：$n≤500,m≤1000$。（下发样例2）
对于100%的数据：$n≤10^5,n−1≤m≤10^5$，保证图连通。
题解
不加赘述了，直入正题
第一步：拆边
突然吗？
那我们先退几步。
其实仔细想过的同学已经咧嘴笑了
不要紧，读完题后我们看一遍数据范围，基本确定复杂度$O(nlogn)$
跑一遍堆优化的$Dijkstra$好像没啥问题，就看能不能跑了。
你发现$dij$要存一个$dis[MAXN]$数组，于是，问题来了。
dis是啥？
你要啥最小就是啥。
因为你要的是合成出来的大数串最小，
其实就是字典序+len比较，
所以你的距离是个字符串。
但，你想想字符串有多长，字符串比较一下大小要花多久。
当然要是您是yzy就当我放了个P
so，肯定是不行滴。
所以这道题严谨的暴力最短路肯定是不行的，
于是定然是贪心啦。
直接裸的BFS是脚指头都会拦着你敲键盘的做法
因为，101明明更短，但你直接贪着走了1 2 3
所以就要拆边
拆边要注意，直接拆无向边会导致来回的路不一样，所以要拆有向边
e.g.
1 <-1137-> 2
|| || ||
\/ \/ \/
-1-> 3 -1-> 4 -3-> 5 -7->
1 2
<-7- 8 <-3- 7 <-1- 6 <-1-
抽象，愿懂中间新加一些无关的点
现在暴力BFS对不对捏
不对，反正你写着写着就发现挂了
准确来说是调试的时候
BFS有个特点，从堆里拿出来的点认为是当前最优解，拿出来后会直接固定下来，后面的点也更新不了它。
那就会导致一个问题：
-3-> 3 -9->
1 2
-3-> 4 -8->BFS从堆里取出1节点后，由于边权一样，就按照默认顺序，把3,4先后入队（堆）。
再先取出3，它只能更新2，便更新了2，4发现2被更新过了，就不更新了。
欸，错了
但是这个消息倒是没那么震惊，咱可以维护维护。
首先，这个堆存不了全局dis，只能局部贪心，那以什么为关键字呢？
第一关键字是数的位数，这个深度可以存，而且位数小的是占绝对优势的。
第二关键字呢，上面连过来的边权很重要，我们暴力BFS就是忽略了这点。
但加上边权后又发现了很大的问题，有些很坏的同层路径由于到子节点的边权小，挤占了最优解，但我们知道字典序要看数的高位，所以我们要维护一下每条路径的排位情况，作为第二关键字，而边权就作为第三关键字
每条路径的排位怎么维护呢？
KX曰：汝会转移乎？
这个思路是超好的，假如上一层深度的排位我们是知道的，对于上一层排位相同的，按照边权排位；否则直接延续上一层排位的相对关系就好了。
自己模拟一下理解更佳
这个方法的正确性不需要证明，如果你知道数学归纳法，那便更一目了然了。
第一层因为只有一个点所以排位肯定是清楚的，接下来按照上述方法转移就对了
具体操作更简单，因为我的堆已经按照关键字排好顺序了，父节点排位相同的并且边权也相同的一定是连续的一段，所以定义一个order作为排位，如果目前节点和上一个从堆里取出的节点的父节点排位相同的并且边权也相同，那order就不++就好了
放代码罢
#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>
#include<queue>
#define int long long
using namespace std;
int n,m;
const int MAXN=1e6+10;
const int mod=1e9+7;
inline int pls(int u,int v){return (u*10+v)%mod;}//进行一个和的加
struct graph{
int to;
int w;
};
vector <graph> g[MAXN*5];
struct node{
int dep;//深度
int fa_ord;//父节点优先级
int w;//这三个都是关键字
int fa_id;//父节点id
int pos;//我把自己都忘了 /kk
node(){}
node(int a,int b,int c,int d,int e){dep=a,fa_ord=b,w=c,fa_id=d,pos=e;}
bool operator <(const node &x)const{
if(dep==x.dep){
if(fa_ord==x.fa_ord)return w>x.w;
else return fa_ord>x.fa_ord;
}
else return dep>x.dep;
}
};
int ans[MAXN*5];
bool vis[MAXN*5];
priority_queue <node> q;
void bfs(){
int order=0;
q.push(node(0,order,0,1,1));
node last=node(-1,-1,-1,-1,-1);//上一个点（其实只用存俩信息，这代码我也看不下去了）
while(!q.empty()){
node now=q.top();
int dep=q.top().dep, fa_ord=q.top().fa_ord, w=q.top().w, fa_id=q.top().fa_id, pos=q.top().pos;//这个是闲的没事干了
q.pop();//你敢信我没加这句T了
if(vis[pos])continue;//《剪枝》
vis[pos]=1;//取出来就是最优点！
ans[pos]=pls(ans[fa_id],w);
if(now.fa_ord!=last.fa_ord || now.w!=last.w)
++order;//第order个确定的点
last=now;
for(auto i:g[pos]){
//更新边
if(vis[i.to])continue;//《剪枝》
q.push(node(dep+1,order,i.w,pos,i.to));
}
}
}
signed main(){
cin>>n>>m;
int cnt=n;
int u,v;
for(int i=1;i<=m;i++){
cin>>u>>v;
if(i<10){
g[u].push_back((graph){v,i});
g[v].push_back((graph){u,i});
continue;
}
//拆边
int t=i,la=u;
while(t>9)g[++cnt].push_back({la,t%10}),t/=10,la=cnt;
g[v].push_back({cnt,t%10});
t=i,la=v;
while(t>9)g[++cnt].push_back({la,t%10}),t/=10,la=cnt;
g[u].push_back({cnt,t%10});
//拆完啦
//这样，就不抽象了吧
}
bfs();
for(int i=2;i<=n;i++)cout<<ans[i]%mod<<endl;
return 0;
}