Animal Run

题意翻译

小动物们厌倦了动物园里的生活,于是决定开展一起大逃亡。 它们偷到了动物园的地图,这是一个$n*m$的网格图,左上角的顶点是逃亡的起点,右下角的顶点是逃亡的终点。图中连满了竖直和水平的道路,还有成$45$°的斜向道路。**它们都是双向边。** ![](https://cdn.luogu.org/upload/pic/42447.png) 不幸的是这个逃亡计划被工作人员看破了,他们将阻止逃亡的发生。图中每一条边上都有一个权值$v_{ij}$,表示有多少个人在此就可以控制这条道路。 现在问**最少**需要多少人,就可以将所有起点到终点的路径控制住。

题目描述

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=446&page=show_problem&problem=4122 [PDF](https://uva.onlinejudge.org/external/13/p1376.pdf)

输入输出格式

输入格式


输出格式


输入输出样例

暂无测试点