CodeForces

题意：给定一个n个点m条边的无向图，边权分别为1-m，从起点1出发，每经过一条边就把边权以字符串的形式加入末尾，求到达其他每个点的最小字符串（长度不同的短的更小，否则字典序小的更小）。

思路很巧妙，将每个边按照边权的位数拆成若干条虚边+若干个虚点，然后以1为起点进行BFS，边权相同的放在一起处理，这样就能保证每个点第一次到达的路径是字符串最小的路径了。

边权排序可以用基排，因为只能取0-9，常数很小。

注意各种细节。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10,inf=0x3f3f3f3f,mod=1e9+7;
int hd[N],ne,n,m,dp[N],tot,buf[N],C[10];
struct E {int u,v,c,nxt;} e[N<<1];
void addedge(int u,int v,int c) {e[ne]= {u,v,c,hd[u]},hd[u]=ne++;}
queue<int> q;
vector<int> vec,vec2;
int upd(int u,int x) {
    if(!~dp[u]) {dp[u]=x,q.push(u); return 1;}
    return 0;
}
void bfs() {
    memset(dp,-1,sizeof dp);
    while(q.size())q.pop();
    upd(1,0),q.push(-1);
    while(q.size()) {
        vec.clear();
        for(; q.front()!=-1; q.pop())vec.push_back(q.front());
        q.pop();
        vec2.clear();
        for(int u:vec)for(int i=hd[u]; ~i; i=e[i].nxt)vec2.push_back(i);
        for(int i=0; i<=9; ++i)C[i]=0;
        for(int i=0; i<vec2.size(); ++i)++C[e[vec2[i]].c];
        for(int i=1; i<=9; ++i)C[i]+=C[i-1];
        for(int i=0; i<vec2.size(); ++i)buf[--C[e[vec2[i]].c]]=vec2[i];
        for(int i=0,j,k; i<vec2.size(); i=j) {
            for(j=i; j<vec2.size()&&e[buf[j]].c==e[buf[i]].c; ++j);
            int f=0;
            for(k=i; k<j; ++k)if(upd(e[buf[k]].v,((ll)dp[e[buf[k]].u]*10+e[buf[k]].c)%mod))f=1;
            if(f)q.push(-1);
        }
    }
}
int main() {
    memset(hd,-1,sizeof hd),ne=0;
    scanf("%d%d",&n,&m);
    tot=n;
    for(int i=1; i<=m; ++i) {
        int u,v;
        scanf("%d%d",&u,&v);
        int c=i;
        if(c/10) {
            addedge(++tot,u,c%10),addedge(++tot,v,c%10),c/=10;
            for(; c/10; c/=10)++tot,addedge(tot,tot-2,c%10),++tot,addedge(tot,tot-2,c%10);
            addedge(v,tot-1,c),addedge(u,tot,c);
        } else addedge(u,v,c),addedge(v,u,c);
    }
    bfs();
    for(int i=2; i<=n; ++i)printf("%d
",dp[i]);
    return 0;
}