#653. [Cnoi2020] 雷雨
[Cnoi2020] 雷雨
题目描述
幻想乡的纵切面可以抽象成一个 的矩形。
其中每一个 的单元格 都有一个电阻计量值(虚构的概念) 。
闪电从雷雨云上的 发出,击中了地面上的红魔馆 与迷途竹林 。
雷电是自然的造物,所以覆盖的位置电阻计量值总和最小,即从 到 与 的两条路径的并集的电阻计量值的和最小。
所以在所有位置电阻计量已知的情况下,Cirno 想知道雷电的经过的路径的最小电阻计量值的和。
输入格式
第一行,五个整数 。$(0
输出格式
一行,一个整数,表示答案。
样例
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
题目来源:洛谷 P6833