CF1209F Koala and Notebook

Link
我们知道最短的路径应该是在位数最少的前提上，从高往低每位尽可能小的答案。
对于一条边，我们将其拆成两条有向的链。
我们把每个点的出边按按长度划分成多个集合，然后分层图bfs即可。

#include<cstdio>
#include<cctype>
#include<vector>
const int N=1000007,P=1000000007;
int a[7],f[N],vis[N];std::vector<int>e[N][10],q[N];
int read(){int x=0,c=getchar();while(isspace(c))c=getchar();while(isdigit(c))(x*=10)+=c&15,c=getchar();return x;}
void add(int u,int v,int w){e[u][w].push_back(v);}
int main()
{
    int n=read(),m=read(),id=n,t;
    for(int i=1,u,v,c,las;i<=m;++i)
    {
	las=u=read(),v=read(),c=0;
	for(int t=i;t;t/=10) a[++c]=t%10;
        for(int j=c,now;j;--j) now=j^1? ++id:v,add(las,now,a[j]),las=now;
	for(int j=c,now;j;--j) now=j^1? ++id:u,add(las,now,a[j]),las=now;
    }
    q[t=1].push_back(1),vis[1]=1;
    for(int i=1;i<=t;++i)
    {
        for(int j=0;j^10;++j)
	{
            int flg=0;
            for(int u:q[i]) for(int v:e[u][j]) if(!vis[v]) vis[v]=1,f[v]=(10ll*f[u]+j)%P,q[t+1].push_back(v),flg=1;
            if(flg) ++t;
        }
    }
    for(int i=2;i<=n;++i) printf("%d
",f[i]);
}