题解 | #最短路径#

借鉴了讨论区大佬的最小生成树思路：第n条边的长度比前面所有n-1条边的长度之和还要大，最短路径一定走的是最小生成树
所以遍历第0到第m-1条边，只保存最小生成树的边，其他的扔掉
同时最小生成树内的最短路径都是唯一的，所以边的长度可以直接取模
最后通过DFS计算出0结点到其余节点的路径长度

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

const int MAX=110;
int father[MAX];
int height[MAX];

struct Edge{
    int to;
    int length;
    Edge(int t,int l):to(t),length(l){}
};

vector<Edge> graph[MAX];

void Initial(int n){
    memset(graph,0,sizeof(graph));
    for(int i=0;i<=n;i++){
        father[i]=i;
        height[i]=0;
    }
}

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

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

bool visit[MAX];

int DFS(int x,int y){
    visit[x]=true;
    for(int i=0;i<graph[x].size();i++){
        if(visit[graph[x][i].to])
            continue;
        if(graph[x][i].to==y)
            return graph[x][i].length;
        int res=DFS(graph[x][i].to,y);
        if(res!=0)
            return (graph[x][i].length+res)%100000;
    }
    return 0;
}

int main(){
    int n,m;
    cin>>n>>m;
    Initial(n);
    int x,y;
    int multiplyer=1;
    for(int i=0;i<m;i++){
        cin>>x>>y;
        if(Find(x)!=Find(y)){  //只有该边构成最小生成树才将其纳入边集
            graph[x].push_back(Edge(y,multiplyer));
            graph[y].push_back(Edge(x,multiplyer));
            Union(x,y);
        }
        multiplyer=(multiplyer*2)%100000;
    }

    for(int i=1;i<n;i++){
        for(int j=0;j<n;j++)
            visit[j]=false;
        int result=DFS(0,i);  //DFS得到0结点到其他结点的距离
        cout<<result<<endl;
    }
}