网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
[HAOI2014]走出金字塔
成绩 | 开启时间 | 2014年09月19日 星期五 10:08 | |
折扣 | 0.8 | 折扣时间 | 2014年09月26日 星期五 10:08 |
允许迟交 | 是 | 关闭时间 | 2014年09月26日 星期五 10:08 |
输入文件 | ha14c.in | 输出文件 | ha14c.out |
【题目描述】
在探险的过程中,考古学家Dr. Kong 无意地被困在一个金字塔中。金字塔中的每个房间都是三角形。Dr. Kong可以破壁走到相邻的房间去。例如,如果他目前处于三角形(2,2)房间,那么他可以破壁走到三角形(2,1)、(2,3)或(1,1)房间。但破壁一面墙需要花费K分钟时间,而考古学家Dr. Kong 的体能只能支持他到S分钟。
好在Dr. Kong手中有这个金字塔地图,他发现金字塔有许多出口,一旦他进入一个有出口的三角形房间,他再用1分钟就可以走出金字塔。
现在,你能否帮助Dr. Kong找到一个走出金字塔花费时间最少的出口?若能,输出Dr. Kong走出金字塔后还剩下的体能时间(应当大于或等于0);若不能,输出-1。
【输入格式】
第一行: N M K S 其中 N表示金字塔的层数;M表示出口数;
K表示破壁一面墙的时间;
S表示考古学家Dr. Kong体能维持分钟数
第二行: Xa Ya 表示考古学家Dr. Kong所在的位置
第3行~M+2行: Xi Yi 表示有出口的三角形坐标位置
【输出格式】
输出Dr. Kong走出金字塔后还剩下的体能时间;若不能,输出-1。
【样例输入】
4 2 2 10 2 1 3 5 4 4
【样例输出】
3
【提示】
【约束条件】
1 <= N <= 1000000 0<=M<=10000 0<K<=20 10<=S<=10000
所有的数据都是整数。数据之间有一个空格
【来源】
在此键入。