#6676. 最小代价路径
-
ID: 6676
传统题
1000ms
256MiB
尝试: 13
已通过: 5
难度: 9
上传者:
hantianliang
标签> 最小代价路径
题面：最小代价路径
时间限制： 1 秒 内存限制： 256 MB
给定一个 n 行 m 列的数字矩阵。
你从左上角 (1, 1) 出发，要走到右下角 (n, m)。
每次只能向右或向下移动一格。进入一个格子时，需要支付该格子的代价，包括起点和终点。
请你计算从左上角走到右下角所需支付的最小总代价。
输入格式
第一行包含两个整数 n, m。
接下来 n 行，每行包含 m 个整数，表示矩阵中每个格子的代价。
输出格式
输出一个整数，表示最小总代价。
数据范围
1 <= n, m <= 100
1 <= ai,j <= 10^6
样例
输入
2 3
1 2 3
1 1 1
输出
4
说明
一种最优走法是：
(1,1) -> (2,1) -> (2,2) -> (2,3)
总代价为：
1 + 1 + 1 + 1 = 4
测试点说明表
| 测试点编号 | n, m ≤ | ai ≤ | 特殊性质 | 设计目的 |
|---|---|---|---|---|
| 1 | 5 | 单格矩阵 | 覆盖起点即终点 | |
| 2 | 5 | 单行矩阵 | 只能一直向右走 | |
| 3 | 4 | 单列矩阵 | 只能一直向下走 | |
| 4 | 3 | 3 | 样例数据 | 对应原程序固定数据，答案为 4 |
| 5 | 100 | 高代价障碍带 | 检查能否绕开高代价格子 | |
| 6 | 9 | 多条路径比较 | 覆盖普通最优路径选择 | |
| 7 | 4 | 中等规模 | 覆盖 DP 状态转移 | |
| 8 | 5 | 10 | 明显通道 | 检查路径选择是否正确 |
| 9 | 6 | 9 | 随机代价 | 覆盖较复杂矩阵 |
| 10 | 1 | 全部代价相同 | 覆盖较大规模和路径长度边界 | |
相关
在以下作业中: