3488.最短路径floyd、并查集

N个城市，标号从 0 到 N−1，M 条道路，第 K 条道路（K 从 0开始）的长度为 2K，求编号为 0的城市到其他城市的最短距离。

输入格式
第一行两个正整数 N,M，表示有 N 个城市，M 条道路。接下来 M 行两个整数，表示相连的两个城市的编号。

输出格式
N−1 行，表示 0 号城市到其他城市的最短路，如果无法到达，输出 −1，数值太大的以 mod100000 的结果输出。

数据范围
2≤N≤100,
1≤M≤500

输入样例：
4 4
1 2
2 3
1 3
0 1

输出样例：
8
9
11

#include<iostream>
#include<cstring>
using namespace std;
const int N=110;
int n,m;
int g[N][N],fa[N];
int find(int x)
{
    if(x!=fa[x]) fa[x]=find(fa[x]);
    return fa[x];
}
int main()
{
    cin>>n>>m;
    memset(g,0x3f,sizeof g);
    for(int i=0;i<n;i++) fa[i]=i;
    for(int i=0;i<n;i++) g[i][i]=0;
    for(int i=0,len=1;i<m;i++,len=len*2%100000)
    {
        int a,b;
        cin>>a>>b;
        if(find(a)!=find(b))
        {
            fa[find(a)]=find(b);
            g[a][b]=g[b][a]=len;
        }
    }
    for(int k=0;k<n;k++)
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
    for(int i=1;i<n;i++){
        if(g[0][i]==0x3f3f3f3f) cout<<"-1"<<endl;
        else  cout<<g[0][i]%100000<<endl;
    }
    return 0;
}