具体的代码的实现,Pirate's Chest

Problem Description
Explorer yy feels lucky that he has got N rather valuable chests by chance. But he had problem opening them. After doing some research for days, he has a clue. Let us number the chests from 1 to N, the chest with number i can be open in three ways:

  1. Open it with the key with number Ai.
  2. Open it with the crowbar with number Bi.
  3. Just open it by force, doing that will decrease yy's HP by Di. yy will die if his HP is less or equal to zero.

Initially, yy has no keys and no crowbars, the tools are stored in a tower which is in the control of monsters. The tower has M floors, every floor can be considered as a 20x20 grids and contains at most two tools, and in case that it contains two tools, those two tools must be the same kind (i.e. both keys or crowbars). Each cell contains either a monster or a tool. If yy stands on a cell with tool, he can pick it up. But if the cell contains a monster, a fight will take place and cost his HP. After the battle this cell will turn into an empty one. On each floor there exist exactly one special "entry" cell, this cell is empty, when yy get to the floor, he will be teleported to that cell immediately. Note that yy can move upstairs or downstairs at any cell.
Once a tool get picked, it can be used arbitary times. It is guaranteed that every tool mentioned will appear at most once.
yy simply hates moving upstairs, as his friend, you're asked to calculate the minimum number of floors yy should go so that he can open all the N chests and still alive, and the minimum total HP cost in above case.

Input
The input contains several test cases, terminated by EOF. Most of test cases are rather small.

In each case first line contains three integer N, M, H (1 <= N <= 30000, 0 <= M <= 1000, 1 <= H <= 109), denotes number of chests, number of floors, and yy's initial health points (HP). Next n lines each contains three integers Ai, Bi and Di (1 <= Ai,Bi <= m, 1 <= Di <= 1000). Next m blocks describing the tower, each block has a 20x20 map describing the floor, the values denotes (suppose the value is x):

(1) 0 <= x <= 1000 : a monster, defeating it will decrease yy's HP by x.
(2) 100000 < x <= 101000 : a key with number x - 100000.
(3) 200000 < x <= 201000 : a crowbar with number x - 200000.
(4) -1 : "entry" cell as we mentioned above.

Output
For each case, if yy cannot survive after having opened all N chests, print one line "Impossible." (without quotes). Otherwise output two integers: the minimum number of floors yy should go and the minimum total HP cost in that case.

Sample Input
3 2 10
2 2 11
1 2 11
2 1 4
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 200002 1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 100001 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 100002 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Sample Output
1 9

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

相似问题

1
各位大牛,菜鸟又遇到一个C语言的难题,写不出来了
1
可能性的判断,输出判定性的结果,用C语言实现
0
一个数列的递推的问题,怎么利用C语言和数据结构解决,最大值是K^2
0
二维字符连通图的问题,运用C语言的知识的综合理解的实现
0
二叉搜索树在数据结构方面的综合运用,如何利用C语言编程解决这个算法?
0
数列的倍增的一个算法题目的求解的过程,如何利用C语言的计算的编程?
2
在猜数游戏中 while 循环里 guess=int(input(""))和 if int(guess) 使用有什么区别呢
0
连通图上的点的可达性的判断的算法问题,怎么利用C语言的程序的设计的方式来实现的?
0
数据结构方面一个数据的整合的算法,利用C程序的语言的编程的技术的实现的做法怎么实现?
0
藏宝地图遍历的一个算法问题,运用数据结构怎么采用C语言的程序的设计的方式实现?
0
确定最后一个海盗与最后一个项目越过木板之前需要多长时间,怎么使用C语言的程序编写代码设计解决
0
统筹优化的时间的问题的求解,要求使用C语言的程序的过程办法的代码的具体的实现的方式是什么的
0
路径搜索计算可以到达宝藏的最短时间,怎么采用C语言的程序代码的设计的过程便写什么代码
1
利用Python运行结果不全,这是为什么?
4
按字符串属性值对对象数组排序
0
Get Luffy Out这个题目的C语言的解法
0
Treasure of the Chimp Island
0
用C语言 Pirate's Chest