关于飞飞侠的近10条评论(全部评论)
spfa无优化可过 rewine 2017-07-21 19:50 4楼
通过这个题，我发现我一直以来的Dijkstra都写错了。。 _Itachi 2017-01-11 17:47 3楼
@_Horizon 膜拜神犇 Hzoi_ 2016-07-06 10:15 2楼
本题是出题人故意用堆优化Dijkstra去卡SPFA的…… 那几个挂掉的提交都来自失败的SPFA作死尝试…… 注意两点：①用vector存邻接表会RE（为何不是MLE？）②数据基本是随机生成的，也就是说步长一般会很大……所以Dijktra占便宜（把那两个点算出来就可以直接跳出），但SPFA+卡时WA了…… cstdio 2014-12-03 20:21 1楼

1837. [国家集训队2011]飞飞侠

★★★ 输入文件：nt2011_fly.in 输出文件：nt2011_fly.out 简单对比
时间限制：5 s 内存限制：512 MiB

飞飞国是一个传说中的国度，国家的居民叫做飞飞侠。飞飞国是一个N×M的矩形方阵，每个格子代表一个街区。

然而飞飞国是没有交通工具的。飞飞侠完全靠地面的弹射装置来移动。

每个街区都装有弹射装置。使用弹射装置是需要支付一定费用的。而且每个弹射装置都有自己的弹射能力。

我们设第i行第j列的弹射装置有Aij的费用和Bij的弹射能力。并规定有相邻边的格子间距离是1。那么，任何飞飞侠都只需要在(i,j)支付Aij的费用就可以任意选择弹到距离不超过Bij的位置了。如下图

（从红色街区交费以后可以跳到周围的任意蓝色街区。）

现在的问题很简单。有三个飞飞侠，分别叫做X，Y，Z。现在它们决定聚在一起玩，于是想往其中一人的位置集合。告诉你3个飞飞侠的坐标，求往哪里集合大家需要花的费用总和最低。（费用相同时优先X，次优先Y）

输入的第一行包含两个整数N和M，分别表示行数和列数。

接下来是2个N×M的自然数矩阵，为Bij和Aij

最后一行六个数，分别代表X，Y，Z所在地的行号和列号。

第一行输出一个字符X、Y或者Z。表示最优集合地点。

第二行输出一个整数，表示最小费用。

如果无法集合，只输出一行NO

4 4

0 0 0 0

1 2 2 0

0 2 2 1

0 0 0 0

5 5 5 5

2 1 3 4 2 2

20% N, M ≤ 10; Bij ≤ 20

40% N, M ≤ 100; Bij ≤ 20

100% 1 ≤ N, M ≤ 150; 0 ≤ Bij ≤ 10^9; 0 ≤ Aij ≤ 1000

国家集训队2011 何朴藩