Minimum Resistance Steiner Tree in a Grid

The cross‐section of Gensokyo can be abstracted as an n×m grid, where each 1×1 cell (i, j) has a resistance measurement value \(R_{i,j}\) (a fictional concept). Lightning emanates from a thundercloud at \(O(n,a)\) and strikes two points on the ground: Red Mansion at \(A(1,b)\) and Lost Bamboo Forest at \(B(1,c)\). Because lightning is a natural creation, it follows two paths (one from \(O\) to \(A\) and the other from \(O\) to \(B\)) such that the sum of the resistance values of all distinct cells over the union of the two paths is minimized. Given the resistance measurements of all cells, your task is to compute this minimum total resistance.

The paths are allowed to move in the four cardinal directions (up, down, left, right) and may share common cells. When a cell is used by both paths, its resistance is counted only once.

Hint: This can be solved by computing the shortest path (with vertex weights) from each of the three terminal points \(O, A, B\). Then, for each cell \(x\), the cost when paths merge at \(x\) is given by:

[ \text{cost}(x) = d_O(x) + d_A(x) + d_B(x) - 2 \times R(x), ]

where \(d_X(x)\) is the minimum resistance cost from terminal \(X\) to cell \(x\) (including the resistance at \(x\)). The final answer is the minimum \(\text{cost}(x)\) over all cells \(x\). Note that the subtraction of \(2R(x)\) is necessary because the resistance of the merging cell \(x\) is counted three times in the sum of the three distances but should only be counted once.

inputFormat

The first line contains two integers \(n\) and \(m\) (the number of rows and columns). The second line contains three integers \(a, b, c\), where the lightning originates from \(O(n, a)\), and the two targets are \(A(1, b)\) and \(B(1, c)\). Then follow \(n\) lines each containing \(m\) integers; the \(j\)-th integer in the \(i\)-th line is \(R_{i,j}\), the resistance measurement of cell \((i,j)\).
Indices are 1-indexed.

outputFormat

Output a single integer, the minimum total resistance value of the union of the two paths.

sample

3 3
2 1 3
1 2 3
4 5 6
7 8 9

21