【bzoj2143】飞飞侠

2014年10月23日2,5610

Description

飞飞国是一个传说中的国度,国家的居民叫做飞飞侠。飞飞国是一个N×M的矩形方阵,每个格子代表一个街区。然而飞飞国是没有交通工具的。飞飞侠完全靠地面的弹射装置来移动。每个街区都装有弹射装置。使用弹射装置是需要支付一定费用的。而且每个弹射装置都有自己的弹射能力。我们设第i行第j列的弹射装置有Aij的费用和Bij的弹射能力。并规定有相邻边的格子间距离是1。那么,任何飞飞侠都只需要在(i,j)支付Aij的费用就可以任意选择弹到距离不超过Bij的位置了。如下图 (从红色街区交费以后可以跳到周围的任意蓝色街区。) 现在的问题很简单。有三个飞飞侠,分别叫做X,Y,Z。现在它们决定聚在一起玩,于是想往其中一人的位置集合。告诉你3个飞飞侠的坐标,求往哪里集合大家需要花的费用总和最低。

Input

输入的第一行包含两个整数N和M,分别表示行数和列数。接下来是2个N×M的自然数矩阵,为Aij和Bij 最后一行六个数,分别代表X,Y,Z所在地的行号和列号。

Output

第一行输出一个字符X、Y或者Z。表示最优集合地点。第二行输出一个整数,表示最小费用。如果无法集合,只输出一行NO

Sample Input

4 4
0 0 0 0
1 2 2 0
0 2 2 1
0 0 0 0
5 5 5 5
5 5 5 5
5 5 5 5
5 5 5 5
2 1 3 4 2 2

Sample Output

Z
15
【范围】
100% 1 < = N, M < = 150; 0 < = Bij < = 109; 0 < = Aij < = 1000

题解

这道题点很少,但是边可能很多,直接建图做最短路显然不可行

但是如果把弹射看成获得了可以走a[i][j]的能量

这样就可以直接最短路了

每走一格消耗1的能量,f[i][j][k]表示在i,j这个点且有k的能量的最少费用

每次只要向四个方向走,或者原地不动即可

做三次最短路