luogu#P6833. [Cnoi2020] 雷雨
[Cnoi2020] 雷雨
题目背景
令人不安的云开始笼罩天空。
巨大的建筑在强风中轧轧作响。
幻想乡中响彻着不和协音。
——「东方辉针城 ~ Double Dealing Character」
一个雷雨交加的夜晚,一束闪电击中了雾之湖畔的红魔馆和迷途竹林。
似乎有什么大事要发生,Cirno 在小屋静静地中思考着。
题目描述
幻想乡的纵切面可以抽象成一个 的矩形。
其中每一个 的单元格 都有一个电阻计量值(虚构的概念) 。
闪电从雷雨云上的 发出,击中了地面上的红魔馆 与迷途竹林 。
雷电是自然的造物,所以覆盖的位置电阻计量值总和最小,即从 到 与 的两条路径的并集的电阻计量值的和最小。
所以在所有位置电阻计量已知的情况下,Cirno 想知道雷电的经过的路径的最小电阻计量值的和。
输入格式
第一行,五个整数 。
以下 行,每行 个整数,表示电阻计量 ,其中第一行表示雷雨云,最后一行表示地面。
输出格式
一行,一个整数,表示答案。
5 5 1 2 4
1 8 1 6 6
1 1 1 2 4
8 3 1 2 2
1 2 1 9 1
1 0 9 1 1
15
提示
样例解释
如图黄色线为闪电的路径。
数据范围与约定
对于 的数据保证:,,。
子任务「本题采用捆绑测试」
- Subtask1(): 。
- Subtask2(): 。
- Subtask3(): 。
- Subtask4(): 。
- Subtask5(): 无特殊限制。