本文共 1210 字，大约阅读时间需要 4 分钟。

Description

设有一棵二叉树（如右图）。其中，圈中的数字表示结点中居民的人口。圈边上数字表示结点编号，现在要求在某个结点上建立一个医院，使所有居民所走的路程之和为最小，同时约定，相邻接点之间的距离为1。如 右图中，若医院建在：

Input

第一行一个整数n，表示树的结点数。（n<=100）

Output

一个整数，表示最小距离和。

Sample Input

5

Sample Output

81

解题思路

先枚举起点，求出最短路后用 最短路 x 人数，比较出最小的

• 输入边的时候，因为是无向图，所以一共要存4条边
• 如果是0，必须排除，不然会连到0，就中断了。

#include
   
    #include
    
     #include
     
      using namespace std;struct DT{   	int to,next;}a[30000];int dis[10000],head[10000],n,num,lt[10000];int h,t,v[10000],f[10000];long long Gun=0x7fffffff;void SPFA(int s){   	memset(f,0,sizeof(f));	h=0,t=1,v[1]=s,dis[s]=0,f[s]=1;	while(h++
      
       0){   //右链接			a[++num].to=y,a[num].next=head[i],head[i]=num;    		a[++num].to=i,a[num].next=head[y],head[y]=num;		}		if(x>0){   //左连接	    	a[++num].to=x,a[num].next=head[i],head[i]=num;	    	a[++num].to=i,a[num].next=head[x],head[x]=num;		}	} 	for(int g=1;g<=n;g++){   //枚举起点		memset(dis,0x7f,sizeof(dis));		SPFA(g);		long long b=0;		for(int i=1;i<=n;i++)		    b+=lt[i]*dis[i]; //人数 x 最短路		Gun=min(Gun,b);	}	printf("%lld",Gun);}