思路：二分答案+dijkstra枚举

可以考虑这样一个问题，当初始的油量越高，越容易抵达终点，因此具有单调性，可以使用二分查找来查询最少需要的初始油量。

然后我们再枚举答案为$x$时，我们需要使用dijkstra查询当前油量是否可以到达终点，如果可以，则$r=mid$，否则$l=mid+1$

具体思路可以查看下面的代码细节。

题目描述

有一辆汽车需要从 $m$ * $n$的地图的左上角（起点）开往地图的右下角（终点 ），去往每一个地区都需要消耗一定的油量，加油站可进行加油

请你计算汽车确保从起点到达终点时所需的最少初始油量

说明：

（1）智能汽车可以上下左右四个方向移动

（2）地图上的数字取值是 $0$ 或 $-1$ 或者正整数：

$-1$：表示加油站，可以加满油，汽车的油箱容量最大为 $100$；

$0$ ：表示这个地区是障碍物，汽车不能通过

正整数：表示汽车走过这个地区的耗油量

（3）如果汽车无论如何都无法到达终点，则返回 $-1$

输入描述

第一行为两个数字，$M$ , $N$，表示地图的大小为 $M$ * $N$ ( $0 < M,N \le 200$ )

后面一个$M$ * $N$ 的矩阵，其中的值是 $0$ 或 $-1$ 或正整数，加油站的总数不超过 $200$个

输出描述

如果汽车无论如何都无法到达终点，则返回-1

如果汽车可以到达终点，则返回最少的初始油量

样例1

输入

2,2
10,20
30,40

输出

70

说明：行走的路线为：右 -> 下

样例2

输入

4,4
10,30,30,20
30,30,-1,10
0,20,20,40
10,-1,30,40

输出

70

说明：行走的路线为：右 -> 右 -> 下 -> 下 -> 下 -> 右

样例3

输入

4,5
10,0,30,-1,10
30,0,20,0,20
10,0,10,0,30
10,-1,30,0,10

输出

60

说明：行走的路线为：下 -> 下 -> 下 -> 右 -> 右 -> 上 -> 上 -> 上 -> 右 -> 右 -> 下 -> 下 -> 下

样例4

输入

4,4
10,30,30,20
30,30,20,10
10,20,10,40
10,20,30,40

输出

-1

说明：无论如何都无法到达终点