1525 - 最短路径2
N个城市，标号从0到N-1，M条道路，第K条道路（K从0开始）的长度为2^K，求编号为0的城市到其他城市的最短距离。
Input
第一行两个正整数N（2<=N<=100）M(M<=500),表示有N个城市，M条道路，
接下来M行两个整数，表示相连的两个城市的编号。
Output
N-1行，表示0号城市到其他城市的最短路，如果无法到达，输出-1，数值太大的以MOD 100000 的结果输出。
Examples
Input
4 3 0 1 1 2 2 0
Output
1 3 -1
Solution C
#include<stdio.h> const int inf=1000000000; const int mod=100000; int p[101],rank[101],d[101][101]; int Find(int i) { if(i==p[i]) return i; else { p[i]=Find(p[i]); return p[i]; } } void Union(int a,int b) { int ta=Find(a),tb=Find(b); if(ta==tb) return; if(rank[a]>=rank[b]) { p[tb]=ta; rank[ta]+=rank[tb]; } else { p[ta]=tb; rank[tb]+=rank[ta]; } } int Pow( long a,long b) { long ret=1; while(b>0) { if(b&1) ret=(ret*a)%mod; b>>=1; a=(a*a)%mod; } return ret; } int main() { int n,m,i,j,k,a,b,ta,tb,dist; while(scanf("%d%d",&n,&m)!=EOF) { for(i=0;i<n;i++) { p[i]=i; rank[i]=1; d[i][i]=0; } for(k=0;k<m;k++) { scanf("%d%d",&a,&b); ta=Find(a); tb=Find(b); if(ta==tb) continue; dist=Pow(2,k); for(i=0;i<n;i++) { if(Find(i)!=ta) continue; for(j=0;j<n;j++) { if(Find(j)!=tb) continue; d[i][j]=(d[i][a]+dist+d[b][j])%mod; d[j][i]=d[i][j]; } } Union(a,b); } ta=Find(0); for(i=1;i<n;i++) { if(Find(i)==ta) printf("%d\n",d[0][i]); else printf("-1\n"); } } return 0; }
Solution C++
#include<stdio.h> const int inf=1000000000; const int mod=100000; int p[101],rank[101],d[101][101]; int Find(int i) { return i==p[i]?i:p[i]=Find(p[i]); } void Union(int a,int b) { int ta=Find(a),tb=Find(b); if(ta==tb) return; if(rank[a]>=rank[b]) { p[tb]=ta; rank[ta]+=rank[tb]; } else { p[ta]=tb; rank[tb]+=rank[ta]; } } int Pow(long long a,long long b) { long long ret=1; while(b>0) { if(b&1) ret=(ret*a)%mod; b>>=1; a=(a*a)%mod; } return ret; } int main() { int n,m,i,j,k,a,b,ta,tb,dist; while(scanf("%d%d",&n,&m)!=EOF) { for(i=0;i<n;i++) { p[i]=i; rank[i]=1; d[i][i]=0; } for(k=0;k<m;k++) { scanf("%d%d",&a,&b); ta=Find(a); tb=Find(b); if(ta==tb) continue; dist=Pow(2,k); for(i=0;i<n;i++) { if(Find(i)!=ta) continue; for(j=0;j<n;j++) { if(Find(j)!=tb) continue; d[i][j]=(d[i][a]+dist+d[b][j])%mod; d[j][i]=d[i][j]; } } Union(a,b); } ta=Find(0); for(i=1;i<n;i++) { if(Find(i)==ta) printf("%d\n",d[0][i]); else printf("-1\n"); } } return 0; }