题解 | #最短路径#

//纯自己写的DFS，竟然一遍就成功了

#include <iostream>
#include <queue>
#include <algorithm>
#include <climits>
#include <cstring>
using namespace std;


int father[101];
int height[101];



void Initial()//每个点都作为根节点，高度都为0
{
    for(int i=0;i<101;i++)
    {
        father[i]=i;
        height[i]=0;
    }
}

int Find(int x)
{
    if(x==father[x])return x;
    return Find(father[x]);
}

void Union(int a,int b)
{
    a=Find(a);
    b=Find(b);
    if(a!=b)
    {
        if(height[a]>height[b])father[b]=a;
        else  if(height[a]<height[b])father[a]=b;
        else
         {
            father[b]=a;height[a]++;
         }
    }
}


struct Edge{
    
    int to;
    int length;
    bool operator<(const Edge& edge) const{
        return length<edge.length;
    }
    Edge(int t,int l)
    {
        to=t;
        length=l;
    }
};


bool visit[101];
vector<Edge> graph[101];

int ans;
void DFS(int f,int t,int a)
{
    if(f==t)
    {
        ans=a;
        return ;
    }

    for(int i=0;i<graph[f].size();i++)
    {
        int u=graph[f][i].to;
        int l=graph[f][i].length;
        if(visit[u])continue;
        else
         {
            visit[u]=true;
            DFS(u,t,a+l);
            visit[u]=false;
         }

    }
}




int main() {
    int n,m;
    while (cin >> n>> m) { 
        Initial();
        int d=1;
        for(int i=0;i<m;i++)
        {
            int a,b;cin>>a>>b;
            
            if(Find(a)!=Find(b))
            {
                Union(a,b);
                graph[a].push_back(Edge(b,d));
                graph[b].push_back(Edge(a,d));
            }
            d=d*2;
            d%=100000;
        }

        //已经得到最小生成树，存在了graph里，下面用DFS来找每个点的距离


        for(int i=1;i<n;i++)
        {
            if(Find(i)!=Find(0))
            {
                cout<<"-1"<<endl;
                continue;
            }
            memset(visit,false,sizeof(visit));
            visit[0]=true;

            ans=0;
            DFS(0,i,0);
            cout<<ans%100000<<endl;
            
        }
     
    }
}