【Solution】Koala and Notebook

xcrr · 2023-08-12 17:57:35 · 题解

这题做法不止一种，我这里讲下 Dijkstra 的做法。

首先拆边，每个边最多拓展 \log_{10}m=5 个边。

距离点 1 相同的点，同时扩展同样的边，扩展出来的点同样距离点 1 相同。（这里距离指的是按照题面方法拼接出的数）。实现就是距离点 1 相同的点放在一个 vector 里，剩下搜索即可。

const int mod=1e9+7;
int nn,n,m,T;
const int N=1e6+10;
vector<int>q[N],G[12][N];
bool vis[N];
int ans[N];
inline void solve(){
    cin>>n>>m;
    nn=n;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        int t=0,t2=0;
        int c[7],b[7];
        int j=i;
        b[++t2]=u;
        while(j){c[++t]=j%10;j/=10;}
        for(int k=1;k<t;k++) b[++t2]=++n;
        b[++t2]=v;
        for(int k=1;k<=t;k++)
        G[c[t-k+1]][b[k]].push_back(b[k+1]);
        b[1]=v,b[t2]=u;
        for(int k=1;k<=t;k++)
        G[c[t-k+1]][b[k]].push_back(b[k+1]);
    }//以上拆边
    //同一个 T 的 q 存的是距离1同“距离”的点。
    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 u:q[i])
            for(auto v:G[j][u])
            {
                if(vis[v])continue;
                flag=vis[v]=1;
                q[T+1].push_back(v);
                ans[v]=(ans[u]*10+j)%mod;
            }
            if(flag)++T;//是否产生了更新。
        }
    }
    for(int i=2;i<=nn;i++)
    cout<<ans[i]<<'\n';
}