九度教程第78题
思路：
由于第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);
}
}
补充：软件开发 , C++ ,
