题目描述
N个城市，标号从0到N-1，M条道路，第K条道路（K从0开始）的长度为2^K，求编号为0的城市到其他城市的最短距离
输入描述:
第一行两个正整数N（2<=N<=100）M(M<=500),表示有N个城市，M条道路 接下来M行两个整数，表示相连的两个城市的编号
输出描述:
N-1行，表示0号城市到其他城市的最短路，如果无法到达，输出-1，数值太大的以MOD 100000 的结果输出。
示例1
输入
复制
4 4 1 2 2 3 1 3 0 1
输出
复制
8 9 11
用大神们的话来说，这是一道披着最短路径外衣的最小生成树的题目。
首先明确一点：1+2^1+2^2+…2^k<2^k+1
刚开始，每一个点属于一个集合，随着最小生成树的建立，最后可以到达的点在一个集合，形成一个连通图
所以，输入的m条边(x,y)，每一条都比之前所有边的和要长，
- 如果x,y在同一个集合，这条边就可以被舍弃了，因为只要xy在一个集合，就说明有从x到y的路径，而这条新路径，一定比已存在的路径要长，所以舍弃
- 如果x,y不在同一个集合，则这条边就是从x到y的最短路径。到这里还没有完成，需要在所有点中找到和x在一个集合的点j，和y在一个集合的点k，由于xy不在同一集合，显然jk也不在同一集合，这一步的作用就是把jk通过xy联系起来，找到从j到k的最短路径，则dis[j][k]=dis[j][x]+len+dis[y][k]，最后Union(x,y)
#include<iostream>using namespace std;
const int MAXN=101;int father[MAXN];
int height[MAXN];
int dis[MAXN][MAXN];
void Init(int n){for(int i=0;i<n;i++){father[i]=i;height[i]=0;for(int j=0;j<n;j++){dis[i][j]=0;}}
}int powmod(int i){int ret=1;while(i--){ret=(ret*2)%100000;}return ret;
}int Find(int i){if(i!=father[i]){father[i]=Find(father[i]);}return father[i];
}void Union(int i,int j){i=Find(i);j=Find(j);if(i!=j){if(height[i]>height[j]){father[j]=i;}else if(height[i]<height[j]){father[i]=j;}else {father[j]=i;height[i]++;}}
}
int main(){int n,m;while(scanf("%d%d",&n,&m)!=EOF){Init(n);int len=1; //路径长度 1,2^1,2^2,2^3,2^4 for(int i=0;i<m;i++){int x,y;scanf("%d%d",&x,&y);if(Find(x)!=Find(y)){ //如果x和y不等，说明他们在两个不同集合中，这条边的长度即为从x到y的最短路径 for(int j=0;j<n;j++){if(Find(x)==Find(j)){ //x和j属于一个集合 for(int k=0;k<n;k++){if(Find(y)==Find(k)) { //y和k属于一个集合，这里的两对分属于两个集合 //将jk通过xy相连起来 dis[j][k]=dis[k][j]=(dis[j][x]+len+dis[y][k])%100000;}}}}}Union(x,y);len=len*2%100000;//如果x和y相等，说明他们在同一个集合中，由于1+2+2^2+2^3+…+2^(k-1)<2^k,所以已有的最短路径就是最长的，这条直接舍弃}int r=Find(0);for(int i=1;i<n;i++){if(Find(i)!=r){dis[0][i]=-1;} printf("%d\n",dis[0][i]);}}
}