题目描述

难度分:$2600$

输入$n(2 \leq n \leq 10^5)$，$m(n-1 \leq m \leq 10^5)$表示一个$n$点$m$边的无向图。节点编号从$1$开始。保证图是连通的。保证图中无自环和重边。

然后输入$m$条边，按照输入的顺序，第$1$条边的边权等于$1$，第$2$ 条边的边权等于$2$，……，第$m$条边的边权等于$m$。

定义$x$到$y$的路径长度，等于依次拼接路径上的边权的结果。例如x-a-b-y路径上的边权从左到右依次为$31,41,59$，那么这条路径的长度等于$314159$。

输出$1$到$2,3,4,…,n$的最短路长度，模$10^9+7$。

注意你要最小化的是最短路长度，然后再取模，不是最小化取模后的值。

输入样例$1$

11 10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11

输出样例$1$

1
12
123
1234
12345
123456
1234567
12345678
123456789
345678826

输入样例$2$

12 19
1 2
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
3 11
11 12
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10

输出样例$2$

1
12
13
14
15
16
17
18
19
1210
121011

输入样例$3$

12 14
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
1 3
1 4
1 10

输出样例$3$

1
12
13
134
1345
13456
1498
149
14
1410
141011

算法

拆边+BFS

这个题的技巧是以前没有见过的，又是学习的一天，虽然灵佬说是一个经典问题“字典序最小最短路”，但是我从来没见过这个经典问题。

拆边

比如$v$到$w$的一条边权为$123$的边，拆分成v-a-b-w，其中v-a的边权为$1$，a-b的边权为$2$，b-w的边权为$3$。

注意拆点后，$v$到$w$和$w$到$v$的边权是不同的，一个是v-a-b-w边权依次为$1,2,3$，另一个是w-b-a-v边权依次为$3,2,1$。 拆边后经过的边数越少，最短路就越小，因此求最短路可以用BFS解决。

BFS

比如从节点$5$出发可以走边权为$0,1,2,…$的边访问某些点，从节点$7$出发走边权为$0,1,2,…$的边访问某些点。与一般BFS不同的地方在于，接下来要访问的点，必须优先访问从节点$5$，$7$出发走边权为$0$的边所到达的点，然后再访问从节点$5$，$7$出发走边权为$1$的边所到达的点，依此类推。这可以保证首次访问到一个点时，我们是通过字典序最小最短路到达的。

所以队列中保存的不是节点，而是节点列表。这个列表中的节点都是走相同的边权到达的。

在BFS的同时用$dist[to] = (dis[from] \times 10 + weight) \% MOD$计算最短路。

复杂度分析

时间复杂度

将每条边进行拆边，时间复杂度为$O(mlog_{10}n)$。接下来进行BFS，需要经过这么多条边，所以时间复杂度也是$O(mlog_{10}n)$，里面用到了优先队列，但由于优先队列中的元素比较少，这里看成一个常数。

综上，整个算法的时间复杂度为$O(mlog_{10}n)$。

空间复杂度

瓶颈在于拆边后得出来的点数，边数和这个点数是一个规模的，接下来是在新图上做BFS，因此额外空间复杂度为$O(mlog_{10}n)$。

C++ 代码

#include<bits/stdc++.h>

using namespace std;

const int N = 2000010, MOD = 1e9 + 7;
struct Node {
    int v, w;
};
vector<Node> edges[N];

int ecnt, n, m, x, y;
int vis[N], dist[N];

struct Edge {
    int u, v, w;
    bool operator<(Edge x) const {
        return w > x.w;
    }
};

void bfs() {
    queue<vector<int>> q;
    q.push({1});
    vis[1] = 1;
    while(!q.empty()) {
        priority_queue<Edge> to;
        vector<int> from, in;
        from = q.front();
        q.pop();
        for(int cur: from) {
            for(auto pir: edges[cur]) {
                int nxt = pir.v, w = pir.w;
                if(!vis[nxt]) {
                    to.push(Edge{cur, nxt, w});
                }
            }
        }
        int weight = to.empty()? 0: to.top().w;
        while(!to.empty()) {
            Edge edge = to.top();
            to.pop();
            if(vis[edge.v]) continue;
            if(weight != edge.w) {
                // 边权不相等时扩展一次队列
                if(!in.empty()) {
                    q.push(in);
                }
                in.clear();
                weight = edge.w;
            }
            vis[edge.v] = 1;
            dist[edge.v] = (10LL*dist[edge.u] + edge.w) % MOD;
            in.push_back(edge.v);
        }
        if(!in.empty()) {
            q.push(in);
        }
        in.clear();
    }
}

int main() {
    scanf("%d%d", &n, &m);
    ecnt = n;
    for(int i = 1; i <= m; i++) {
        scanf("%d%d", &x, &y);
        stack<int> stk;
        queue<int> q;
        int num = i;
        // 拆边
        while(num) {
            stk.push(num % 10);
            q.push(num % 10);
            num /= 10;
        }
        if(stk.size() == 1) {
            // 没办法拆边
            edges[x].push_back(Node{y, i});
            edges[y].push_back(Node{x, i});
        }else {
            // 拆出来的新边要增加ecnt
            ++ecnt;
            edges[x].push_back(Node{ecnt, stk.top()});
            edges[ecnt].push_back(Node{x, q.front()});
            stk.pop();
            q.pop();
            while(stk.size() > 1) {
                edges[ecnt].push_back(Node{ecnt + 1, stk.top()});
                edges[ecnt + 1].push_back(Node{ecnt, q.front()});
                ecnt++;
                stk.pop();
                q.pop();
            }
            edges[y].push_back(Node{ecnt, q.front()});
            edges[ecnt].push_back(Node{y, stk.top()});
            ++ecnt;
            stk.pop();
            q.pop();
        }
    }
    bfs();
    for(int i = 2; i <= n; i++) {
        printf("%d\n", dist[i]);
    }
    return 0;
}