题目简述

给定一个网格，每个单元格代表不同的通信方式及代价。起点为左上角 (0, 0)，终点为右下角 (n-1, m-1)，你需要计算从起点到终点的最小代价路径。路径只能在上下左右四个方向移动，且不能穿越值为-1的单元格。如果无法到达终点，返回-1。

通信方式的代价分别为：

• 3: 有线通信
• 20: 短波通信
• 13: 超短波通信

题目内容

往往由于地理位置、距离等各种因素影响需要使用有线、无线等手段进行混合组网，然而每种通信方式的代价都不尽相同，比如有线组网时延就比无线组网低很多，由于数据传输过程中需要经过多个节点，而且每个节点间连线方式不同，所以合理路由算法就显得格外的重要。现假设我们有3 种通信方式及代价:有线【$Wire$&$3$】、短波【$Short wave$&$20$】、超短波【$Ultra short wave$&$13$】。

现给出一个$m*n$组网图(矩阵表示，数字分别是$3/20/13$，其中$-1$说明没有链接)，求出从$S$起点到$E$终点的最优路径的代价和，其中$-1$不能作为路径上的节点且路径仅支持上下左右四个方向。

输入描述

第一行:输入$n[1,10^6]$; $m [1,10^6]$，描述矩阵的大小

第二行:输入整型矩阵，，每一个元素使用代价$【3、20、13、-1】$做为填充值;$3$代表有线，$20$代表短波，$13$代表超短波，$-1$代表未链接。

说明: 起点$S$为$[0,0]$

终点$E$为$【n-1,m-1】$

输出描述

输出组网单包最小代价路径，如果无法到达，返回$-1$。

样例1

输入

3 3
{{3,20,13},{-1,-1,3},{-1,-1,3}}

输出

42

说明

3 20 13
-1 -1 3
-1 -1 3

唯一的路线是$3->20->13->3->3$

样例2

输入

3 3
{{3,20,13},{3,-1,3},{3,3,3}}

输出

15

说明

3 20 13
3 -1 3
3 3 3

最小代价路线$3->3->3->3->3$;还有一条路线的是$3->20->13->3->3$大于最小路径