3678: 上街(第六轮04)
题目描述
牛牛注意到家周围的红绿灯排布可以看成一个 nx m 的方格图，位置从左上角的 (1,1)到右下角的(n,m)，右上角为(1,m)。地图是上北下南左西右东的。
牛牛计算好了每个路口向下走到下一个路口的时间di 和向右走到下一个路口需 要花费的时间 ei 。
在每个路口，向前或向左走只有在绿灯时才可以前进，向右走则可以忽略红绿灯， 通过路口的时间可以忽略不计。某些路口没有加装红绿灯， 这些路口可以选择任 意方向前进而不需要等待。
每个路口的红绿灯有自己独立的时间，分别是东西（左右）方向的ai 秒绿灯和南 北（上下）方向的bi 秒绿灯， 东西方向为绿灯时南北方向为红灯， 南北方向为绿 灯时同理，初始时所有红绿灯都在南北方向红灯第0秒（如第i个路口，初始之后 是南北方向是ai 秒红灯， 随后是bi 秒绿灯， 然后是ai 秒红灯， 以此类推）。为了简 化问题，设定t = a i + bi，对于所有红绿灯， 红灯加绿灯的时间是一样的。如果 ai = bi = 0，则表示该路口未加装红绿灯。
牛牛喜欢欣赏沿途的风景，唯独不喜欢等红绿灯，所以对他来说，等待红绿灯的 时间在他看来时间会流逝缓慢许多。而且，他不会在一条道路的中途停下等时间， 除非是等红绿灯。
他认为的花费代价 = 红绿灯等待时间 x 10 + 路途花费时间（不含等红绿灯） 牛牛一开始在位置(1,1)点朝下（南）骑行（等待红绿灯），他希望到达路口 (xe, ye) （任意方向均可），想知道最小花费的代价是多少 。
输入
第一行输入三个整数n, m, t，表示地图的大小，和红绿灯的总时长（ai + bi）。 第二行输入两个整数xe, ye，表示牛牛要到达的终点。
随后 n*m 行，每行输入四个整数ai, bi, di, ei，分别为位置(i/m + 1(整除),i%m + 1) 的红灯时间、绿灯时间，向下到下一个路口的距离和向右到下一个路口的距离。
对于边缘位置给出的，通向地图之外的di, ei应该忽略。
对于 30%的数据， n, m ≤ 3。
另有 10%的数据， n ≤ 1或 m ≤ 1。
对于总量 30%的数据， ai, bi = 0 。 以上三种数据共占 60%。
对于 100%的数据有1 ≤ n, m ≤ 200, 0 ≤ ai, bi ≤ t ≤ 60,0 ≤ di, ei ≤ 10^4 。 数据规模阶梯型增大。
输出
一行输出一个整数，即花费的最小代价。
样例输入 复制
2 3 30
2 3
15 15 15 30
15 15 60 15
0 0 100 0
15 15 0 70
15 15 0 30
20 10 0 0
样例输出 复制
270提示
【样例 1 输入】
2 3 30
2 3
15 15 15 30
15 15 60 15
0 0 100 0
15 15 0 70
15 15 0 30
20 10 0 0
【样例 1 输出】
270
【样例 1 说明】
有几条可选的路线，我们分别来分析一下：
一开始需要在(1,1)等 15 秒的红灯，代价是 150。
路线 1: (1,1) -> (1,2) 路程花费时间 30， (1,2)->(1,3) ，正值东西方向红灯，等 待 15 秒， 代价 150， 路程花费 15， (1,3)->(2,3)，此时因为是右转，不需要等待 红 绿 灯 （而 且 这 里 也 未 加 装 红 绿 灯 ）， 路 程 花 费 100 ， 共 计 代 价 150+30+150+15+100 = 445 。
路线 2: (1,1) -> (1,2) 路程花费时间 30， (1,2)->(2,2) 右转忽略红绿灯，路程花 费 60，(2,2)->(2,3)，此时时间为 105，正值南北方向绿灯，路程花费 30，共计代 价 150+30+60+30 = 270 。
路线 3: (1,1) -> (2,1) 路程花费时间 15， (2,1)->(2,2)， 正值南北方向红灯，等待 15 秒，代价 150， 路程花费 70， (2,2)->(2,3) 正值东西方向红灯， 等待 5 秒，代 价 50，路程花费 30，共计代价 150+15+150+70+50+30=465 。
可能还有一些其他路线，如(1,1)->(2,1)->(2,2)->(1,2)->(1,3)->(2,3)，代价更高一 些，综上，最小代价为 270 。
对于 30%的数据， n, m ≤ 3。
另有 10%的数据， n ≤ 1或 m ≤ 1。
对于总量 30%的数据， ai, bi = 0 。 以上三种数据共占 60%。
对于 100%的数据有1 ≤ n, m ≤ 200, 0 ≤ ai, bi ≤ t ≤ 60,0 ≤ di, ei ≤ 10^4 。 数据规模阶梯型增大。