P3659 [USACO17FEB] Why Did the Cow Cross the Road I G

奶牛为什么要过马路？其中一个原因是 Farmer John 的农场有很多道路，使得他的奶牛在四处走动时不可避免地要穿过许多道路。 FJ 的农场被安排成一个 $N \times N$ 的方形网格田地（$3 \leq N \leq 100$），其中有 $N-1$ 条南北向的道路和 $N-1$ 条东西向的道路穿过农场内部，作为田地之间的分隔。农场外部有一圈高高的围栏，防止奶牛离开农场。奶牛 Bessie 可以自由地从任何田地移动到相邻的田地（北、东、南或西），只要她在穿过分隔两块田地的道路时小心地左右看看。她穿过一条道路需要花费 $T$ 单位时间（$0 \leq T \leq 1,000,000$）。 有一天，FJ 邀请 Bessie 去他家进行一场友好的国际象棋比赛。Bessie 从西北角的田地出发，而 FJ 的家在东南角的田地，因此 Bessie 需要走很长一段路。由于她在路上会感到饥饿，她会在每经过第三个田地时停下来吃草（不包括她的起始田地，但可能包括最终到达的 FJ 家的田地）。有些田地的草比其他田地更茂盛，因此停下来吃草所需的时间取决于她停下的田地。 请帮助 Bessie 确定她到达 FJ 家所需的最少时间。

无

无

这个例子的最优解是向东移动 3 个方格（吃“10”），然后向南移动两次，向西移动一次（吃“5”），最后向南和向东移动到目的地。