题解 | #最短路径#

• 比较懒，不想写大数处理（Dijkstra+大数计算）
• 借鉴MST的思想，MST+DFS即可
• 因为本题MST确定之后，最短路径也是唯一确定的

#include<iostream>
#include<cstring>
#include<cmath>
#include<vector>
#include<climits>
using namespace std;

const int maxn=501;
const int INF=INT_MAX;

int father[maxn];//并查集
int height[maxn];
void Initial(int n){
  for(int i=0;i<n;i++){
    father[i]=i;  
    height[i]=1;
  }
}

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

void Union(int x,int y){
  int a=Find(x);
  int b=Find(y);
  if(a==b)return;
  else 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 distance;
  Edge(int t,int d):to(t),distance(d){}
  Edge(){}
};

vector<Edge>graph[maxn];//图的邻接矩阵
int dis[maxn];
bool visit[maxn];

void dfs(int x,int cur){//DFS统计路径长度（访问结点、当前长度）
    visit[x]=true;
    for(int i=0;i<graph[x].size();i++){
        int next=graph[x][i].to;//下一结点
        int d=graph[x][i].distance;
        if(visit[next])continue;
        else{
            dfs(next,(cur+d)%100000);//递归
            dis[next]=(cur+d)%100000;
        }
    }
}

int main(){
  int n,m;
  while(scanf("%d%d",&n,&m)!=EOF){
    if(n==0)break;
    Initial(n);//并查集初始化
    int d=1;
    for(int i=0;i<m;i++){
      int from,to;
      scanf("%d%d",&from,&to);
      if(Find(from)!=Find(to)){//不在同一集合的点，添加边
          Union(from,to);
          graph[from].push_back(Edge(to,d));//无向边
          graph[to].push_back(Edge(from,d));
      }
      d=d*2;
      d=d%100000;//更新边长
    }
      
      fill(dis,dis+n,INF);
      dis[0]=0;
      fill(visit,visit+n,false);
      dfs(0,0);
      for(int i=1;i<n;i++){
          if(dis[i]==INF)printf("-1\n");
          else printf("%d\n",dis[i]);
      }
  }
  return 0;
}