2 shunfurh shunfurh 于 2017.09.02 17:39 提问

Guarding Zion

Problem Description
It is the 22th century, and machines with supreme artificial intelligence have conquered the world. Humans are kept alive by a computer controlled program, the Matrix, for no other purpose than providing energy to the machines. Only a small group of freedom fighters have escaped the Matrix and built a secret resist base, Zion, near the core of the earth. However the machines have discovered this and send down millions of sentinels to destroy Zion.

The underground world is actually the sewers of the previous cities in ruin -- gigantic tunnels connecting the ground, Zion, and various other intersections. However all sewers have been destroyed when the machines first conquered the mankind. Because of limited time, the sewers have been repaired by people from Zion such that there will always be no more than one path from one intersection to another. No tunnel connects an intersection to itself. The best weapon we have is EMP (electromagnetic pulse) charge, an extremely powerful weapon to use against machines. Blowing an EMP charge will cause any electronic device within its range to stop functioning, therefore destroying the machines within range completely. However it can also cause another EMP charge within the range to malfunction, so the distance between any two EMP charges must be no less than their range.

The council has decided to put EMP on certain intersections to minimize the possibility of the machines destroying Zion. Since our resources are limited, we can only afford to put EMP charges on certain intersections of the underground tunnels. Deploying an EMP charge on a certain intersection has a non-negative cost. What is the maximal distance you can cover with EMP charges, and what's the minimum cost to achieve that maximal distance?

Input
There are multiple test cases in the input file. Each test case starts with three integers N , M and D , (2<=N<=300, 1<=M<=3000) , the number of intersections, the number of edges, and the range of each EMP charge, respectively. Intersections are numbered from 0 to N - 1 . The following line consists of N integers, the cost of deploying an EMP charge on intersection i . The next M lines each consists of three integers S , T , and C , (0<=S, T<=N - 1, 1<=C<=20000) , meaning that intersection S and T are connected by a tunnel whose length is C . Every test case ends with one blank line indicating the end of test case.

N = 0 , M = 0 , D = 0 indicates the end of input file and should not be processed by your system.

Output
For each test case, output two integers in the format as indicated in the sample output: the maximum distance EMPs can cover and the minimum cost you've found on a single line.

Sample Input
2 1 3
5 6
1 0 6

0 0 0

Sample Output
Case 1: 6 11

1个回答

caozhy
caozhy   Ds   Rxr 2017.09.17 00:26
已采纳
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
11214 - Guarding the Chessboard(暴力搜索)
IDA*算法, 从小到大枚举深度上限,不过该题是有深度上限的,题目中的第一个样例表明:最多需要5个皇后就可以覆盖整个棋盘 。  利用紫书上的技巧,我们可以快速的判断任意两个棋子是不是在同一行、同一列、同一对角线 (详情见紫书P193那两个图)。  这样之后暴力搜索就可以了 。 每一层需要O(nm)的复杂度,但是实际上并不需要那么大的复杂度 。和八皇后问题类似 , 当前行之前的行已经放置了皇后,
EOJ 2521 Guarding the Farm
题目大意: 统计图中具有相同元素的连通块个数,需保证该连通块周围的所有元素都比连通块元素小。 思路:DFS入门题 #include #include using namespace std; int dx[] = {-1,-1,-1, 0, 0, 1, 1, 1}; int dy[] = {-1, 0, 1,-1, 1,-1, 0, 1}; int n, m, flag; in
bzoj1619【Usaco2008 Nov】Guarding the Farm 保卫牧场
DFS
UVa11214 - Guarding the Chessboard
给出m*n棋盘上的目标点,求最少用几个皇后可以守卫所有目标点。  类似八皇后做法,2维数组标记行、列、主对角线、副对角线。  有个加速的技巧,测试之后发现10*10的棋盘全部守卫至少需要5个,所以上限就是5,当maxd等于5时直接输出,不进行搜索。 #include #include using namespace std; const int maxn=11; int n,m,t,maxd
寻找 Zion
越来越觉得 The Matrix 真是一部伟大的电影,直接预言了中国互联网的发展趋势。最近接而连三的网络屏蔽事件已经快让人喘不过气来。我相信有一天那群人会在你的身体内植入电子芯片,控制你的的身体与思想,"帮助"你在和谐中得到永生。 "你有狼牙棒,我有天灵盖",即使是网络顺民,最终也会在这样的层层阉割与过滤下激起反抗。总会有人冲破层层封锁,到达锡安(Zion) ,在 Matrix 中被解放的人都
zion语言编辑器
简单易用,适合初学!
Guarding the Farm
Guarding the FarmTime Limit: 1000 ms     Memory Limit: 65536 KBTotal Submit: 23     Accepted: 18 DescriptionThe farm has many hills upon whi
Liang的Rootkit习作-ZION
Liang把Rootkit实现习作晒出来,程序测试运行在Windows XP SP2上。除小部分涉及利用Windows或HIPS商业产品中潜在设计缺陷实现隐藏或者逃避的技巧代码已经隐去之外,完整代码可在下面下载,如有指正、交流可以通过chenliang0817@hotmail.com与他取得联系。Liang对习作的简单介绍如下:Win32平台下的Rootkit习作 Codename: Zion b
好用的簡報模版,用了會上癮的
ppt模板下载, ZION, 保證好用,這可是國外專業的顧問公司的
Top 10 Open Source Web Application Firewalls (WAF) for WebApp Security
Web application firewalls provide security at the application layer. Essentially, WAF provides all your web applications a secure solution which ensures the data and web applications are safe.  A