摘要：
P1364 医院设置 P1364医院设置的标题描述中有一个二叉树，如图所示：圆圈中的数字表示节点中的居民人口。圆边上的数字表示节点编号。现在需要在一个节点上建立一个医院，以最小化所有居民所需的距离总和。同时，同意相邻节点之间的距离为l。如上图所示，如果医院建在一个地方，距离之和=4+12+2*20+2*40=136；如果医院建在三个位置，距离之和=4*2+13+20+40=81…输入和输出样本输入样本1:5132340012452004000输出样本#1:81显示为树：#include#include#include#include#includeusingspacestd；组成N=200；组成最大n=9999999；intnow=1；头部[N]；intdis[N]；intpeople[N]；布尔维斯[N]；整数，x，y；队列＜int＞q；结构节点｛intu，v，w，nxt；｝E[N]；inlinethread（）｛intx=0；charc=getchar（）；whilec=getchar（）；whelex=x*10+c-'0'，c=getchar（）；returnx；｝inlinevoidadd｛E[现在].v=v；E[现在].w=1；E[当前].nxt=头[u]；头[u]=现在++；｝inlinevoidspfa{fordis[i]=Maxn，vis[i]=0；dis[start]=0；vis[start]=1；q.push；while（！
题目描述
设有一棵二叉树，如图：
其中，圈中的数字表示结点中居民的人口。圈边上数字表示结点编号，现在要求在某个结点上建立一个医院，使所有居民所走的路程之和为最小，同时约定，相邻接点之间的距离为l。如上图中，
若医院建在1 处，则距离和=4+12+2*20+2*40=136；若医院建在3 处，则距离和=4*2+13+20+40=81……
输入输出格式
输入格式：第一行一个整数n，表示树的结点数。(n≤100)
接下来的n行每行描述了一个结点的状况，包含三个整数，整数之间用空格(一个或多个)分隔，其中：第一个数为居民人口数；第二个数为左链接，为0表示无链接；第三个数为右链接。
输出格式：一个整数，表示最小距离和。
输入输出样例
输入样例#1：
5 13 2 3 4 0 0 12 4 5 20 0 0 40 0 0
输出样例#1：
81
化树为图：
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<queue> using namespace std; const int N=200; const int Maxn=9999999; int now=1; int head[N]; int dis[N]; int people[N]; bool vis[N]; int n,x,y; queue<int>q; struct node{ int u,v,w,nxt; }E[N]; inline int read() { int x=0; char c=getchar(); while(c<'0'||c>'9')c=getchar(); while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar(); return x; } inline void add(int u,int v) { E[now].v=v; E[now].w=1; E[now].nxt=head[u]; head[u]=now++; } inline void spfa(int start) { for(int i=1;i<=n;i++) dis[i]=Maxn,vis[i]=0; dis[start]=0; vis[start]=1; q.push(start); while(!q.empty()) { int top=q.front(); q.pop(); vis[top]=0; for(int i=head[top];i!=-1;i=E[i].nxt) { if(dis[E[i].v]>dis[top]+E[i].w) { dis[E[i].v]=dis[top]+E[i].w; if(!vis[E[i].v]) vis[E[i].v]=1,q.push(E[i].v); } } } } int main() { n=read(); for(int i=1;i<=n;i++) head[i]=-1; for(int i=1;i<=n;i++) { people[i]=read(); x=read(); y=read(); if(x) add(i,x),add(x,i); if(y) add(i,y),add(y,i); } int answer=Maxn; for(int i=1;i<=n;i++) { spfa(i); int ans=0; for(int j=1;j<=n;j++) ans+=dis[j]*people[j]; answer=min(ans,answer); } printf("%d",answer); return 0; }