【题解-信息学奥赛一本通】1338：【例3-3】医院设置

题目1338【例3-3】医院设置题目描述设有一棵二叉树如下图其中圈中的数字表示结点中居民的人口圈边上数字表示结点编号。现在要求在某个结点上建立一个医院使所有居民所走的路程之和为最小同时约定相邻结点之间的距离为1。就本图而言若医院建在1处则距离和4122×202×40136若医院建在3处则距离和4×213204081……输入第一行一个整数n表示树的结点数n≤100。接下来的n行每行描述了一个结点的状况包含三个整数整数之间用空格一个或多个分隔其中第一个数为居民人口数第二个数为左链接为0表示无链接第三个数为右链接为0表示无链接。输出一个整数表示最小距离和。时空限制1s / 64MB样例输入5 13 2 3 4 0 0 12 4 5 20 0 0 40 0 0样例输出81代码#includebits/stdc.husingnamespacestd;constintN10010;intn,e,l,r,ans1e9,dis[N],per[N];vectorintg[N];intbfs(intsx){memset(dis,-1,sizeofdis);dis[sx]0;queueintq;q.push(sx);intsum0;while(!q.empty()){inttq.front();q.pop();for(inti0;ig[t].size();i){intug[t][i];if(dis[u]-1){dis[u]dis[t]1;sumdis[u]*per[u];q.push(u);}}}returnsum;}intmain(){cinn;for(inti1;in;i){cinelr;per[i]e;if(l)g[i].push_back(l),g[l].push_back(i);if(r)g[i].push_back(r),g[r].push_back(i);}for(inti1;in;i)ansmin(ans,bfs(i));coutans;return0;}结果