题目链接:http://acm.swust.edu.cn/problem/412/
![[Swust OJ 412]--医院设置(floyd算法) [Swust OJ 412]--医院设置(floyd算法)](https://image.shishitao.com:8440/aHR0cDovL2Jic21heC5pa2FmYW4uY29tL3N0YXRpYy9MM0J5YjNoNUwyaDBkSEJ6TDJsdFlXZGxjekF1WTI1aWJHOW5jeTVqYjIwdllteHZaekl3TVRVdk5qZzNPVEkxTHpJd01UVXdOaTh5TmpFMk1EQTFNVGMxTWpreE1qZ3VaMmxtLmpwZw%3D%3D.jpg?w=700&webp=1)
![[Swust OJ 412]--医院设置(floyd算法) [Swust OJ 412]--医院设置(floyd算法)](https://image.shishitao.com:8440/L3Byb2dyYW0gZmlsZXMgKHg4NikvMzYwc2U2L1VzZXIgRGF0YS90ZW1wLzY5M2NkNTgxZzk5ZTEwNjZkNjgyOCY2OTAuZ2lm.gif?w=700&webp=1)
![[Swust OJ 412]--医院设置(floyd算法) [Swust OJ 412]--医院设置(floyd算法)](https://image.shishitao.com:8440/L3Byb2dyYW0gZmlsZXMgKHg4NikvMzYwc2U2L1VzZXIgRGF0YS90ZW1wLzY5M2NkNTgxZzk5ZTEwNjZkNjgyOCY2OTAuZ2lm.gif?w=700&webp=1)
其中,圈中的数字表示结点中居民的人口。圈边上数字表示结点编号,现在要求在某个结点上建立一个医院,使所有居民所走的路程之和为最小,同时约定,相信接点之间的距离为1。如上图中,若医院建在:
1处,则距离和=4+12+2*20+2*40=136
3处,则距离和=4*2+13+20+40=81
……
接下来的n行每行描述了一个结点的状况,包含三个整数,整数之间用空格(一个或多个)分隔,其中:第一个数为居民人口数;第二个数为左链接,为0表示无链接;第三个数为右链接。
5
13 2 3
4 0 0
12 4 5
20 0 0
40 0 0
|
81 |
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define inf 0x3f3f3f int n, ptr[], mpt[][], L, R;
void Floyd(){
for (int k = ; k <= n; k++){
for (int i = ; i <= n; i++){
for (int j = ; j <= n; j++)
mpt[i][j] = min(mpt[i][j], mpt[i][k] + mpt[k][j]);
}
}
}
int main(){
int i, j, sum, tmp;
while (cin >> n){
sum = inf;
memset(mpt, inf, sizeof(mpt));
for (i = ; i <= n; i++){
cin >> ptr[i] >> L >> R;
mpt[L][i] = mpt[i][L] = mpt[R][i] = mpt[i][R] = ;
}
Floyd();
for (i = ; i <= n; i++){
tmp = ;
for (j = ; j <= n; j++) {
if (i != j)
tmp += mpt[i][j] * ptr[j];
}
sum = min(sum, tmp);
}
cout << sum << endl;
}
return ;
}
[Swust OJ 412]--医院设置(floyd算法)的更多相关文章
-
[Swust OJ 767]--将军回家(Dijkstra算法)
题目链接:http://acm.swust.edu.cn/problem/767/ Time limit(ms): 1000 Memory limit(kb): 65535 Description ...
-
SWUST OJ 1075 求最小生成树(Prim算法)
求最小生成树(Prim算法) 我对提示代码做了简要分析,提示代码大致写了以下几个内容 给了几个基础的工具,邻接表记录图的一个的结构体,记录Prim算法中最近的边的结构体,记录目标边的结构体(始末点,值 ...
-
Floyd算法应用-医院选址问题
1)问题描述 n个村庄之间的交通图可以用有向网图来表示,图中边<vi, vj>上的权值表示从村庄i到村庄j的道路长度.现在要从这n个村庄中选择一个村庄新建一所医院,问这所医院应建在哪个村庄 ...
-
洛谷P1364 医院设置(Floyd)
题目描述 设有一棵二叉树,如图: 其中,圈中的数字表示结点中居民的人口.圈边上数字表示结点编号,现在要求在某个结点上建立一个医院,使所有居民所走的路程之和为最小,同时约定,相邻接点之间的距离为l.如上 ...
-
【6.10校内test】T2 医院设置
医院设置[题目链接] 感觉我超废 我是一个连floyd都不会写了的灵魂OI选手qwq(考场上写了半天spfa然后写炸了(微笑)) floyd的暴力: 1.先建树:用邻接矩阵存.存之前记得先初始化为IN ...
-
最短路径—Dijkstra算法和Floyd算法
原文链接:http://www.cnblogs.com/biyeymyhjob/archive/2012/07/31/2615833.html 最后边附有我根据文中Dijkstra算法的描述使用jav ...
-
Floyd算法(三)之 Java详解
前面分别通过C和C++实现了弗洛伊德算法,本文介绍弗洛伊德算法的Java实现. 目录 1. 弗洛伊德算法介绍 2. 弗洛伊德算法图解 3. 弗洛伊德算法的代码说明 4. 弗洛伊德算法的源码 转载请注明 ...
-
Floyd算法(二)之 C++详解
本章是弗洛伊德算法的C++实现. 目录 1. 弗洛伊德算法介绍 2. 弗洛伊德算法图解 3. 弗洛伊德算法的代码说明 4. 弗洛伊德算法的源码 转载请注明出处:http://www.cnblogs.c ...
-
Floyd算法(一)之 C语言详解
本章介绍弗洛伊德算法.和以往一样,本文会先对弗洛伊德算法的理论论知识进行介绍,然后给出C语言的实现.后续再分别给出C++和Java版本的实现. 目录 1. 弗洛伊德算法介绍 2. 弗洛伊德算法图解 3 ...
随机推荐
-
python引用py文件中文报错
文件 a.py 中引用文件 b.py 如果文件b.py中包含中文,会报错. 文件hello.py中代码如下: def say_nihao(): print "你好" 文件main. ...
-
c#中浅拷贝和深拷贝的理解
c#中拷贝有浅拷贝和深拷贝之分. 例如对象A,其中有值类型字段和引用类型字段: 1.浅拷贝: 对于值类型字段,直接逐位复制到新拷贝的副本对象中,修改副本的字段的值,不会影响源对象中字段的值: 对于引用 ...
-
Css3_写出小广播样子
/* create an arrow that points up */ div.arrow-up { width:0px; height:0px; border-left:5px solid tra ...
-
bzoj1054
弱弱的搜索题, 我的做法是将矩阵看做二进制然后用位运算来做的,感觉比较舒服 ..] ,,,); dy:..] ,,-,); type node=record po,next: ...
-
Acdream1157---Segments (CDQ分治)
陈丹琦分治~~~其实一些数据小的时候可以用二维或者多维树状数组做的,而数据大的时候就无力的题目,都可以用陈丹琦分治解决. 题目:由3钟类型操作:1)D L R(1 <= L <= R &l ...
-
leetcode第一刷_Merge Sorted Array
水题,只是思想还是实用的. 当然能够新建出一个数组.比較着拷贝过去.可是没有必要啊亲.想想为什么用源数组会麻烦,由于确定了前面的数.为了后面的数字不被覆盖,要依次往后移,转念一想,先确定后面的数字.就 ...
-
理解git对象
1. 首次提交,提交一个简单的文件 a.txt ,commit 之后的图如下: 如图所示,生成了 3 个对象,一个 commit 对象,一个 tree 对象,一个 blob 对象.图上蓝底是 co ...
-
DNS架设准备+申请领域查询授权
1. 架设DNS服务器首先我们得安装一下的软件[root@bogon ~]# rpm -qa | grep ^bindbind-libs-9.8.2-0.37.rc1.el6.i686 <==给 ...
-
STM32标准IIC驱动
IIC(Inter-Integrated Circuit)总线是一种由 PHILIPS 公司开发的两线式串行总线,用于连接 微控制器及其外围设备.也是目前很流行的通讯总线,使用IIC总线做产品能够很大 ...
-
24.Django路由规则
路由规则 1.基于正则的url 在templates目录下创建index.html.detail.html文件 (1)index.html <!DOCTYPE html> <html ...