---
title: "最低通行费"
created: 2025-11-28
tags:
  - 算法
---

# 最低通行费

## 题目 [最低通行费](https://blog.csdn.net/weixin_43972154/article/details/124090750)

![[image-4381a554.png]]

![[image-41bbe36e.png]]

## 思路分析

![[image-f9204c76.png]]

通过案例模拟可以发现其实很像图论里的dfs问题 （这里好像可以用最短路 发现每一步好像都是贪心选的最小 或许拿这道题来分析迪杰斯特拉和spfa好像更合适）

但这题用暴搜的话会超时

也不难发现和摘花生差不多 不过是多了两个东西——可以从上下左右走

这里有个证明 说只能往右和往下走最优 然后就是完全一样的摘花生题

起点是左上角的方块 (1,1)，而终点是右下角的方块 (n,n) 而每次移动，只能走到四相邻的格子中

四相邻：

我们常在一个矩阵中说四相邻，说的就是以当前格子为中心，上、下、左、右四个方向相邻的格子

也就是对于(x,y)来说的(x−1,y),(x+1,y),(x,y−1),(x,y+1)的四个格子

因此，我们在矩阵中找任意两个点之间的距离，用到的不是欧式距离，而是曼哈顿距离

![[image-1041d70f.png]]

这题用的就是曼哈顿距离

我们可以模拟一下(1,1)到(2,2)的曼哈顿距离，答案是2 而我们从(1,1)出发走到(2,2)的最短距离路线分别是，路线长度也是2 而对于起点的(1,1)到终点(n,n)，它们之间的曼哈顿距离是2n−2
而本题又要求我们在 2n−1的时间内，从起点走到终点

因此，得出结论，我们的走的路线不是完全随机的，而是遵循最短路的原则走的

也就是说，每次移动，至少要使曼哈顿距离缩短 1 于是，规定了我们每次在不越过边界的情况下只能向右或向下移动

emm

反正照着摘花生的写法来就行了 此时属性变成了min

状态表示：f[i][j]：所有从起点出发 走到ij坐标处的所有方案中总价值最小的

状态转移：f[i][j]=min(f[i-1][j],f[i][j-1])+w[i][j];

![[image-51ee5179.png]]

因为是最小值 之前在背包dp中也分析过了

初始化的时候要除第一个位置外都置为inf

一个拓展知识点：

**min怎么传多个参数**

在C++11之前，`min`函数只接受两个参数，但是C++11引入了可变参数模板的概念，这使得`min`函数能够接受任意数量的参数。这种参数传递方式称为初始化列表（initializer\_list）。

在这个特定的情况中，`min`函数接受了一个由大括号包围的初始化列表，其中包含了三个值：`f[i][j]`、`f[i][j - 1] + w[i][j]`、`f[i - 1][j] + w[i][j]`。这些值将被逐个比较，然后返回最小的那个值。

所以，`min`函数在这里的语法是这样的：

`min({value1, value2, value3, ...});`

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=110;

int w[N][N];

int f[N][N];

int n;

int main()

{

    cin>>n;

    for(int i=1;i<=n;i++){

        for(int j=1;j<=n;j++){

            cin>>w[i][j];

        }

    }

    memset(f,0x3f,sizeof f);

    f[1][1]=w[1][1];

    for(int i=1;i<=n;i++){

        for(int j=1;j<=n;j++){

            /*

            这里需要特判（1，1）

            如果不特判（1，1）分别可以从（1，0）or（0，1）过来

            这两点的值为正无穷，且f[i][j]的属性是min

            f[1][1]是从这两个无穷大的数更新过来的

            摘花生不用特判的原因是求得max

            （1，1）无论从（1，0）or（0，1）来都是0

            所以不影响结果不需要特判

            */

            if (i == 1 && j == 1)

                f[i][j] = w[i][j];

            else

                f[i][j] = min(f[i][j - 1], f[i - 1][j]) + w[i][j];

            //或者直接用这个 合并 省去特判

            //f[i][j]=min({f[i][j], f[i][j - 1] + w[i][j], f[i - 1][j] + w[i][j]});

        }

    }

    cout<<f[n][n];

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[方格取数|方格取数]] 🏠 [[00-刷题理模型]] ➡️ [[友好城市|友好城市]]