数组在图上的移动的一个算法的问题,要综合运用C语言知识的程序的编写

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

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问

相似问题

0
序列三元组的计算的算法问题运用的C语言的编程技术如何结局
0
综合运用C语言的编程的技术如何解决这里的数列求和的算法问题呢
0
一个序列求极值的一个算法的问题,要运用C语言的办法如何才能解决呢
0
数据结构对于棋盘的一个分割子的算法的问题,运用C语言技术的编程实现
0
多行对偶匹配数组的一个算法问题,运用C语言编程的技术的实现的做法
0
数组移动转换的问题的求解方式,怎么利用C语言算法的实现
0
高阶图形的算法问题,图像的匹配数运用C语言程序算法实现怎么实现
0
32位的整数的运算实现IP地址的算法,C语言的字符数组的运用怎么做
0
数组的有序的重新排列的一个算法的实现的问题,怎么利用C语言的办法?
0
迷宫的绕路的一个算法问题,如何运用C语言的程序的编写的方式实现
0
运用数据结构去实现纸牌的移动的一个算法,怎么采用C语言的程序的代码的编写的技术实现的?
3
合理使用算法运用C语言, 计算出给定数各个位上数字为偶数的和怎么做?
0
区间线段的搜索问题的综合运用,怎么使用C语言的程序编写的程序的格式来实现算法的解答
1
求一个代码c语言实现图的深度遍历(递归)、非递归算法以及实现图的广度遍历(队列)
0
最小费用建模的一个算法问题,要求使用的C语言的程序的编写怎么来做的
1
算法分组问题,一个班n个人进行分组,每组最多k个人,有两个要求,组与组之间人数最多相差1,队伍数要尽可能少。
2
悬赏Java语言怎么编写冒泡算法,对5个数字进行排序,而且数字是存放再数组里的
1
Java语言如何实现一个算法
0
利用普利姆算法和克鲁斯卡尔算法实现最小生成树问题C语言或者C++语言实现
0
Java语言排序函数算法不改变原来的数组的顺序,使用return返回结果怎么写呢