题解 | #最短路径# Floyd + 并查集

#include <iostream>
using namespace std;

const int N = 110;
const int INF = 0x3f3f3f3f;
const int MOD = 100000;

int n, m;
int path[N][N];
int p[N], vis[N];

void init(int n)
{
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            path[i][j] = INF;
    for(int i = 0; i < n; i++)
    {
        p[i] = i;
        vis[i] = 0;
    }
}

int find(int x)
{
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}

int main() {
    while(cin >> n >> m)
    {
        int from, to;
        init(n);
        int dis = 1;
        for(int i = 0; i < m; i++)
        {
            cin >> from >> to;
            int x = find(from);
            int y = find(to);
            if(x != y)    //如果已在同一个连通分支，则不用更新距离，因为2^k > 2^k-1 + 2^k-1 ... + 1
            {
                p[x] = y;
                path[from][to] = path[to][from] = dis;
            }
            dis *= 2;
            dis %= MOD;
        }
        
        vis[0] = 1;
        int min_dis, min_node;

        //方法一
        // for(int k = 0; k < n; k++)    //Floyd   写起来简单，就是时间复杂度高
        //     for(int i = 0; i < n; i++)
        //         for(int j = 0; j < n; j++)
        //             path[i][j] = min(path[i][j], path[i][k] + path[k][j]);

        //方法二
        for(int i = 0; i < n; i++)        //Floyd的优化
        {
            min_dis = 1111111;
            min_node = 0; 
            for(int j = 1; j < n; j++)
            {
                if(!vis[j] && min_dis > path[0][j])
                {
                    min_node = j;
                    min_dis = path[0][j];
                }
            }
            vis[min_node] = 1;
            for(int j = 1; j < n; j++)
            {
                if(!vis[j] && path[0][j] > path[0][min_node] + path[min_node][j])
                    path[0][j] = path[0][min_node] + path[min_node][j];
            }
        }

        for(int i = 1; i < n; i++)
            if(path[0][i] == INF) puts("-1");
            else cout << path[0][i] % MOD << endl;
    }
}