拆边+BFS队列骚操作——cf1209F

这个拆边+队列操作实在是太秒了

队列头结点存的是一个存点集的vector，1到这个点集经过的路径权值是一样的，所以向下一层拓展时，先依次走一遍每个点的0边，再走1边。。。以此类推，能保证最后走出来的路径是最优的

/*
拆边+将每个点的边按权值排序+BFS 
*/
#include<bits/stdc++.h>
#include<vector>
using namespace std;
#define N 1000005
#define ll long long 
#define mod 1000000007

ll n,m;
struct Edge{ll v,w;};
//bool operator<(Edge&a,Edge&b){return a.w<b.w;}
vector<int>G[N][10];
vector<int>q[N];//队列里面是一堆结点

ll ans[N],vis[N];

int main(){
    cin>>n>>m;int nn=n;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        int w[6]={},len=0,t=i;
        while(t){
            w[++len]=t%10;t/=10;
        }
        int l=1,r=len;
        while(l<r){
            swap(w[l],w[r]);
            ++l,--r;
        }
        
        int pre=u;
        for(int j=1;j<=len;j++){
            int newnode;
            if(j==len)newnode=v;
            else newnode=++n;
            G[pre][w[j]].push_back(newnode);
            pre=newnode;
        }
        pre=v;
        for(int j=1;j<=len;j++){//反向边也要反着加 
            int newnode;
            if(j==len)newnode=u;
            else newnode=++n;
            G[pre][w[j]].push_back(newnode);
            pre=newnode; 
        }
    }
    
    int head=0,tail=0;
    q[++tail].push_back(1);vis[1]=1;
    for(;head<=tail;head++){
        for(int i=0;i<=9;i++){//先走队列头结点所有元素的0... 
            int flag=0;
            for(auto u:q[head]){
                for(auto v:G[u][i])if(!vis[v]){
                    vis[v]=flag=1;
                    q[tail+1].push_back(v);
                    ans[v]=(ans[u]*10+i)%mod;
                }
            }
            if(flag)tail++;            
        }
    } 
     
    
    for(int i=2;i<=nn;i++)
    cout<<ans[i]<<'
';
}