从Prim算法和Dijkstra算法两种算法异同的角度说明为何本题最小生成树中包含了所有最短路径。

两种思路：

  • 最短路+高精度加乘（最容易想到的方法，该题大数可以用二进制数组表示比较方便）
  • 最小生成树+dfs

这里着重记录第二种思路。首先说明一下为什么最小生成树中包含了所有最短路径。

这里不得不提及一下Prim算法和Dijkstra算法，这两种算法有极高的相似度，这两个算法在添加新结点时，都是选择“距离最短”的结点加入集合，但是Prim算法中，“距离最短”是指未访问的结点到已经访问的所有结点距离最小，即将已经访问的结点视为一个整体，将距离最小的结点加入到已访问的集合中；而在Dijkstra算法中，“距离最短”是指所有未访问结点（通过已访问的结点）到源点距离最小。

简单来说，Prim算法是选离已访问集合最近的点加入集合，而Dijkstra算法选离源点最近的点加入集合。

而本题显然两种算法选点是完全一致的，因为边权值以2倍递增，从二进制的视角看，低位若干位的二进制1的加和肯定小于高位的一个1，如1000B大于0111B，因此就算把集合内的所有边的权值相加，都不会大于集合外的任意两边的边权值差值，故离源点最近的点就是离集合最近的点。

因此最小生成树中包含了所有最短路径。而因为输入是边权是递增有序的，所有下述代码选择的是kruskal算法（利用并查集实现）求最小生成树。

//
// Created by Zed on 2024/2/8.
//
#include <iostream>


using namespace std;
const int MAXN = 1e3;
int father[MAXN];
const int INF = 1e7;
const int M = 100000;
struct Edge {
    int w, nex, to;
};


struct Graph {
    int h[MAXN];
    Edge edges[MAXN * MAXN];
    int cnt;

    void addEdge(int u, int v, int w) {
        cnt++;
        edges[cnt].w = w;
        edges[cnt].to = v;
        edges[cnt].nex = h[u];
        h[u] = cnt;
    }

    int d[MAXN];

    long long fastPow(long long a, long long  b, long long  MOD) {
        long long  ans = 1;
        while (b) {
            if (b & 1) {
                ans = (ans * a) % MOD;
            }
            a = (a * a) % MOD;
            b >>= 1;
        }
        return ans;
    }

    bool v[MAXN];

    void dfs(int root, int sum) {//在得到最小生成树后，直接dfs即可获得答案
        d[root] = sum;
        v[root] = true;
        for (int i = h[root]; i; i = edges[i].nex) {
            if (v[edges[i].to]) {
                continue;
            }
            dfs(edges[i].to, (sum + fastPow(2, edges[i].w, M)) % M);
        }
    }

    void init() {
        cnt = 0;
        for (int i = 0; i < MAXN; ++i) {
            v[i]= false;
            d[i]=-1;
        }
    }
} graph;

int find(int x) {
    return x == father[x] ? x : father[x] = find(father[x]);
}

int main() {
    int n, m;
    while (cin >> n >> m){
        graph.init();
        for (int i = 0; i < n; ++i) {//初始化并查集
            father[i] = i;
        }
        for (int i = 0; i < m; ++i) {
            int u, v;
            cin >> u >> v;
            if (find(u) != find(v)) {
                graph.addEdge(u, v, i);
                graph.addEdge(v, u, i);
                father[find(u)] = find(v);
            }
        }
        graph.dfs(0, 0);
        for (int i = 1; i < n; ++i) {
            cout << graph.d[i] << endl;
        }
    }
    return 0;
}