题目名称	1681. [HAOI 2014]走出金字塔
输入输出	`ha14c.in/out`
难度等级	★
时间限制	1000 ms (1 s)
内存限制	256 MiB
测试数据	10
题目来源	cqw 于2014-07-18加入
开放分组	全部用户
提交状态
分类标签	HAOI
	分享题解

通过：26，提交：90，通过率：28.89%
AAAAAAAAAA	100	0.000 s	0.00 MiB	C++
kxxy	100	0.000 s	0.00 MiB	C++
Samle	100	0.000 s	0.00 MiB	C++
Fmuckss	100	0.006 s	0.39 MiB	C++
Satoshi	100	0.009 s	0.31 MiB	C++
cstdio	100	0.010 s	0.28 MiB	C++
铁策	100	0.010 s	0.28 MiB	C++
Dijkstra	100	0.010 s	0.31 MiB	C++
石家庄二中教练	100	0.010 s	0.31 MiB	C++
mikumikumi	100	0.011 s	0.31 MiB	C++

本题关联比赛
防止浮躁的小练习v0.4

关于走出金字塔的近10条评论(全部评论)
mdzz没有读入起点还能过一个点 kZime 2017-03-26 21:11 4楼
占楼 NVIDIA 2016-03-14 19:16 3楼
推了一中午公式，第一次用数学规律，爽得不行（^_^）~~~ slyrabbit 2015-03-16 18:40 2楼
第5组数据，原先数据中的答案是695，但我的程序跑出来是659，手测(217,66)到(212,49)的答案也是659，所以我就把数据改了……如果有问题找我 cstdio 2014-08-28 11:43 1楼

1681. [HAOI 2014]走出金字塔

★ 输入文件：ha14c.in 输出文件：ha14c.out 简单对比
时间限制：1 s 内存限制：256 MiB

【题目描述】

在探险的过程中，考古学家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。

【样例输入】

【样例输出】

【提示】

【约束条件】

1 <= N <= 1000000 0<=M<=10000 0<K<=20 10<=S<=10000

所有的数据都是整数。数据之间有一个空格

【来源】

在此键入。