原题出处：CF1209F
数据太难造了，卡掉了比较显然的暴力，但是很多假做法就卡不掉了，所以赛时放了一些假做法高分。
10分：暴力dfs找到1号点到其他城市的所有路径，一旦更新了答案再继续 dfs下去即可。
30分：直接无脑用string来做dijkstra，复杂度刚刚够用。
100分：
做法1： 考虑先求出从起点到每一个点的最小数字串长度，注意，此处我们只是关心串的长度。
做完这个事情以后，哪些边是有可能被用到的，就已经确定好了。
我们此时对所有可能被用到的边进行拆边，例如一条边编号是364，我们就拆成3,6,4的三条边。
接下来，从起点出发进行dfs，每次贪心的走当前编号最小的边，如果对应的点还没有被走过，就走过去。
#include<bits/stdc++.h>
#define mod 1000000007
#define maxn 100005
#define ll long long
#define mk(a,b) make_pair(a,b)
using namespace std;
int n,m,tot,len[maxn];
basic_string<pair<int,int>> edge[maxn],E[maxn*6];
int cal(int x) {int ret=0; while (x) {ret++; x=x/10;} return ret;}
struct nod{
int id,d;
nod(){}
nod(int a,int b) {id=a; d=b;}
bool operator<(const nod&x)const{return d>x.d;}
};
void addedge(int u,int v,int ID)
{
int c[8],id[8],cnt=0;
while (ID) {c[++cnt]=ID%10; ID/=10;}
for (int i=cnt;i>=2;i--) id[i]=++tot;
id[1]=v; id[cnt+1]=u;
for (int i=cnt+1;i>=2;i--) E[id[i]]+=mk(id[i-1],c[i-1]);
return;
}
int cmp(pair<int,int> x,pair<int,int> y) {return x.second<y.second;}
priority_queue<nod> Q;
int vis[maxn],dis[maxn];
void dijk()
{
memset(dis,0x3f,sizeof(dis)); dis[1]=0;
Q.push(nod(1,0));
while (!Q.empty())
{
nod now=Q.top(); Q.pop();
if (vis[now.id]) continue;
vis[now.id]=1;
for (auto nxt:edge[now.id])
{
if (dis[nxt.first]>now.d+len[nxt.second])
{
dis[nxt.first]=now.d+len[nxt.second];
Q.push(nod(nxt.first,dis[nxt.first]));
}
}
}
// for (int i=1;i<=n;i++) cout<<dis[i]<<" ";
for (int i=1;i<=n;i++)
for (auto nxt:edge[i])
if (dis[i]+len[nxt.second]==dis[nxt.first])
{
addedge(i,nxt.first,nxt.second);
}
for (int i=1;i<=tot;i++) sort(E[i].begin(),E[i].end(),cmp);
}
int ans[maxn*5];
void dfs(int i)
{
// cout<<i<<" "<<ans[i]<<endl;
for (auto nxt:E[i])
if (!ans[nxt.first] && nxt.first!=1)
{
ans[nxt.first]=(ans[i]*10ll+nxt.second)%mod;
dfs(nxt.first);
}
}
int main()
{
cin>>n>>m;
for (int i=1;i<=m;i++) len[i]=cal(i);
tot=n; int u,v;
for (int i=1;i<=m;i++) {cin>>u>>v; edge[u]+=mk(v,i); edge[v]+=mk(u,i);}
dijk();
dfs(1);
for (int i=2;i<=n;i++) cout<<ans[i]<<endl;
}
但实际上上述做法是错的哦。（我专门写了这个做法，用来造数据的时候卡掉它）。
举一个反例：
节点1有好几个出边，出边都是3，一个是338拆出来的，一个是33拆出来的。
这时候你先搜哪一个3都不对，因为你并不知道那个33后面跟的是6还是9（PS：33后面跟的是DAI）。
所以这个做法是假的，但造数据的人还是很良心的造了45分。
做法2：
我们一开始就把边拆好，所有边长度都是 1 每次扩展的时候，把一次性能扩展出的长度一样，且字典序一样的边都扩展出来。
具体是：对于当前所有距离一模一样的点，存入同一个 vector，然后一起枚举他们的编号为 的出边，一次性把相同距离的点都扩展出来，翻译成代码长这样：
vector<int> G[N][10], q[N];
for(int i = 1; i <= T; ++ i) {
for(int j = 0; j <= 9; ++ j) {//优先走数字小的
bool flag = 0;
for(auto it : q[i])//对于同一个i,q[i]中的点的ans都是一样的
for(auto v : G[it][j]) {
if(vis[v]) continue;
vis[v] = flag = 1;
q[T+1].push_back(v);
ans[v] = (10ll*ans[it]+j) % mod;//更新答案
}
if(flag) T++; //如果有拓展出新的节点，则下一次拓展出的点要放到不同的vector中
}
}
完整的代码：
//格外注意一个细节就是，我们需要开9n*10个大约9e6个vector，这是300mb的静态空间，如果无脑开2e7个vector就会MLE，一分没有。
int cnt;
int ans[N];
bool vis[N];
vector<int> G[N][10], q[N];
int main() {
int n, m;
read(n,m);
cnt = n;
for(int i = 1; i <= m; ++ i) {
int u, v;
read(u,v);
int tmp = i, pre = v;
while (tmp>9) {
G[++cnt][tmp%10].push_back(pre);
tmp/=10;pre=cnt;
}
G[u][tmp].push_back(pre);
tmp = i, pre = u;
while(tmp>9) {
G[++cnt][tmp%10].push_back(pre);
tmp/=10;pre=cnt;
}
G[v][tmp].push_back(pre);
}
int T;
q[++T].push_back(1);
vis[1] = 1;
for(int i = 1; i <= T; ++ i) {
for(int j = 0; j <= 9; ++ j) {//优先走数字小的
bool flag = 0;
for(auto it : q[i])//对于同一个i,q[i]中的点的ans都是一样的
for(auto v : G[it][j]) {//走过就不用再走了
if(vis[v]) continue;
vis[v] = flag = 1;
q[T+1].push_back(v);
ans[v] = (10ll*ans[it]+j) % mod;//更新答案
}
if(flag) T++;
}
}
for(int i = 2; i <= n; ++ i) cout << ans[i] << endl;
}