题目描述(ID:12373)
标题: 开车车
标签:
详情:
作为啊哈星球的头号领袖,啊哈沃德有自己的司机。司机更想把车开成极品飞车,但是在星球上不得不遵守交规。星球并不是特别大,所以交通系统也并不复杂。星球上的道路规划十分规整,将城市分成一个一个小方块。城市整体为正方形,边长N个街区。
        现在是下班时间。当车经过绿灯路口的时候自然会十分顺畅,但是红灯路口会十分拥挤-取决于有多少辆车堵在路口。这时就不得不等前面的车起步加速。那么有多少辆呢?谁知道。虽然交管部门利用大数据成功推算了车辆数量与拥挤等候时间的关系,究竟有多少辆车仍然没有规律可循。啊哈沃德要从西北角出发,到达位于东南角的家。
        但是你也不会一路顺(绿)(),根据车速不同,每经过T个路口就会恰好赶上一个红灯。这时就需要再另外等候的时间。每经过一个绿灯,消耗的时间都是K
啊哈沃德是一个注重效率的人。他希望用最少的时间到家。交管部门在网上实时提供全城的车流量,于是他要求他的司机送他出发前看一眼全城车流量,找最快的路回家。
        司机算了三天后放弃了,说他的头痛的不行。所以这锅现在丢给你了。请告诉啊哈沃德,最快多久可以到家。哦对了,从(1,1)出发时一定是绿灯,不会被堵在那里的喵。到达(n,n)的时候如果有红灯也是要等的喵。
                    注:司机除了被堵以外,不能在道路上停留。
输入格式:
第一行为三个整数N,K和T,
接下来N行每行N个整数,其中第i+1行第j列表示当在(i,j)路口遭遇红灯需要等待的时长。
输出格式:
第一行为三个整数N,K和T,
接下来N行每行N个整数,其中第i+1行第j列表示当在(i,j)路口遭遇红灯需要等待的时长。
限制: 对于30%测试点,T=1
对于所有数据,均满足:1<=N<=100,10<=P(i,j)<=1,000,000,T<=50
样例:

输入

5 4 1
100 70 22 86 82
51 65 26 39 55
93 31 24 19 80
74 23 54 64 6
66 54 62 33 9

输出

272
登录并解答