编程介的小学生 2019-02-12 19:20 采纳率: 20.5%
浏览 186

数组在图上的移动的一个算法的问题,要综合运用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

  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥15 求差集那个函数有问题,有无佬可以解决
    • ¥15 【提问】基于Invest的水源涵养
    • ¥20 微信网友居然可以通过vx号找到我绑的手机号
    • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
    • ¥15 解riccati方程组
    • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
    • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
    • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
    • ¥50 树莓派安卓APK系统签名
    • ¥65 汇编语言除法溢出问题