思路： 由於第i條邊的權值w[i] = 2^i，那麼前i-1條邊的權值之和為w[0]+w[1]+·+w[i-1] =（2^i）-1 也就是說前i-1條邊的權值之和小於第i條邊。 根據這一性質，當添加第i條邊（a，b）時： 也就是說前i-1條邊的權值之和小於第i條邊。 根據這一性質，當添加第i條邊（a，b）時： 若a，b未連通，則a，b間的最短路徑為w[i]； 若a，b已經連通，則a，b之間的最短路徑保持不變。 C語言源碼： [cpp] #include<stdio.h> #define maxsize 110 #define M 100000 int T[maxsize]; int E[maxsize][maxsize]; int visited[maxsize]; int findroot(int x) { int temp; if(T[x]==-1) return x; else { temp=findroot(T[x]); T[x]=temp; return temp; } } void dfs(int x,int n,int sum) { int i; for(i=0;i<n;i++) if(visited[i]==0&&E[x][i]!=0) { visited[i]=1; T[i]=sum+E[x][i]; dfs(i,n,T[i]); } } int main() { int m,n,a,k,b,i,j,num,sum,roota,rootb; while(scanf("%d %d",&n,&m)!=EOF) { for(i=0;i<n;i++) { T[i]=-1; visited[i]=0; } for(i=0;i<n;i++) for(j=0;j<n;j++) E[i][j]=0; k=1; for(i=0;i<m;i++) { scanf("%d %d",&a,&b); roota=findroot(a); rootb=findroot(b); if(roota!=rootb) { T[rootb]=roota; E[a][b]=k%M; E[b][a]=k%M; } k=(k*2)%M; } i=0; sum=0; visited[0]=1; for(i=1;i<n;i++) T[i]=-1; dfs(0,n,sum); for(i=1;i<n;i++) printf("%d\n",T[i]%M); } }
