题目分析

这道题要求找到一种方式，以最少的公交乘坐次数游览完所有景点。我们可以把这道题理解成一个访问所有点至少一次的最短路径问题。类似于经典的旅行商问题（TSP），但稍有不同的是——每个景点允许重复访问。

思路：Floyd 最短路 + 状压 DP

为了解决这个问题，我们将使用 Floyd-Warshall 算法结合状态压缩动态规划（DP），来找到访问所有景点的最短路径（即乘坐公交的最少次数）。其中，Floyd-Warshall 用于预处理两点之间的最短路径，状态压缩 DP 则用于计算如何最少次数地遍历所有景点。

思路详解

1. 预处理最短路径（Floyd-Warshall 算法）：

   由于我们要访问所有景点且每个景点可以重复访问，因此我们只关心任意两个景点之间的最短路径距离。Floyd-Warshall 算法能够在 O(n^3) 的时间内找到图中所有节点对之间的最短路径。

   • 构建一个二维数组 dist，其中 dist[i][j] 表示景点 i 到景点 j 的最短路径距离。
   • 初始化时，dist[i][j] = 1（如果 i 和 j 之间有公交连接），否则设为一个极大值（如 10^9）表示不可达。
   • 然后利用 Floyd-Warshall 算法迭代更新 dist[i][j]，找到任意两点之间的最短路径距离。

2. 状态压缩动态规划（DP）：

   由于最多只有 20 个景点，我们可以使用一个整数的二进制位来表示景点的访问状态。例如，00001 表示只访问了景点 0，11111 表示访问了 5 个景点。我们定义一个 DP 数组 dp[j][i]，表示在访问状态 i 下，到达景点 j 所需的最少公交次数。

   • 初始化状态：每个景点 j 在只访问自己的状态 1 << j 下的公交次数为 0，即 dp[j][1 << j] = 0。

   • 状态转移：对于每一个可能的状态 i 和在该状态下被访问的每一个景点 j，我们尝试从其他已访问的景点 k 转移到 j，并更新 dp[j][i]。

     • 设 last = i ^ (1 << j) 为去掉景点 j 后的状态，遍历所有景点 k，若 k 在 last 状态中已被访问，则 dp[j][i] 更新为：dp[j][i] = min(dp[j][i], dp[k][last] + dist[k][j])。

3. 计算结果：

   • state 的最终状态为 2^n - 1，即所有景点都已访问。我们遍历所有景点 i，计算在状态 state - 1 下访问所有景点的最小公交次数。
   • 若 ans 仍为 10^9，则无法访问所有景点，输出 0；否则输出 ans。

$Q$:这样做是否会和$dp$的定义有冲突？因为在走最短路的过程中,有些路径上的点已经被访问过了，但是我们的$dp$并没有更新他们？

没有冲突。因为我们$dp$定义的访问或没访问，是人为的定序，是为了保证能够访问过所有可能情况。而不是看它实际被访问过没。

代码

java

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 读取景点数量
        int n = sc.nextInt();
        int[][] edge = new int[n][n];
        
        // 读取公交路线的二维数组
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                edge[i][j] = sc.nextInt();
            }
        }

        // 初始化距离数组dist，初始值设为一个很大的数（10^9），表示不可达
        int[][] dist = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dist[i], (int) 1e9);
            dist[i][i] = 0;
        }

        // 根据输入的公交线路设置初始直达距离
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (edge[i][j] == 1) {
                    dist[i][j] = 1;
                }
            }
        }

        // 使用Floyd-Warshall算法计算所有景点之间的最短路径
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }

        // 使用状态压缩DP来记录到达每个状态时的最少公交次数
        int state = 1 << n;
        int[][] dp = new int[n][state];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], (int) 1e9);
            dp[i][1 << i] = 0;
        }

        // 遍历所有可能的状态i（从1到2^n-1）
        for (int i = 1; i < state; i++) {
            for (int j = 0; j < n; j++) {
                if ((i & (1 << j)) == 0) continue;
                int last = i ^ (1 << j);
                for (int k = 0; k < n; k++) {
                    if ((last & (1 << k)) == 0) continue;
                    if (dp[k][last] == (int) 1e9) continue;
                    dp[j][i] = Math.min(dp[j][i], dp[k][last] + dist[k][j]);
                }
            }
        }

        // 最终答案，遍历所有景点，在访问所有景点的状态（state - 1）下找到最小公交次数
        int ans = (int) 1e9;
        for (int i = 0; i < n; i++) {
            ans = Math.min(ans, dp[i][state - 1]);
        }

        // 输出结果，如果ans仍然是初始值，说明无法访问所有景点，输出0，否则输出ans
        if (ans == (int) 1e9) {
            System.out.println(0);
        } else {
            System.out.println(ans);
        }
        
        sc.close();
    }
}

python

# 读取景点数量
n = int(input())

# 读取公交路线的二维数组
edge = [list(map(int, input().split())) for _ in range(n)]

# 初始化距离数组dist，初始值设为一个很大的数（10^9），表示不可达
dist = [[10 ** 9] * n for _ in range(n)]

# 自己到自己距离为0
for i in range(n):
    dist[i][i] = 0

# 根据输入的公交线路设置初始直达距离
for i in range(n):
    for j in range(n):
        if edge[i][j] == 1:  # 如果景点i和景点j之间有公交路线
            dist[i][j] = 1   # 直达距离设为1

# 使用Floyd-Warshall算法计算所有景点之间的最短路径
for k in range(n):
    for i in range(n):
        for j in range(n):
            # 更新dist[i][j]，通过中间景点k找到更短路径
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

# 使用状态压缩DP来记录到达每个状态时的最少公交次数
state = 1 << n  # 总的状态数量为2^n
dp = [[10 ** 9] * state for _ in range(n)]  # 初始化DP数组，初始值为10^9，表示不可达

# 初始化DP状态，每个景点作为起点时的状态
for i in range(n):
    dp[i][1 << i] = 0  # 从每个景点开始只访问自己的状态，公交次数为0

# 遍历所有可能的状态i（从1到2^n-1）
for i in range(1, state):
    # 遍历所有景点j，如果景点j在状态i中被访问
    for j in range(n):
        if (i >> j) & 1 == 0:  # 如果状态i中没有访问景点j，跳过
            continue
        # 计算上一个状态last，表示状态i中去掉景点j后的状态
        last = i ^ (1 << j)
        # 遍历景点k，尝试从景点k到达景点j
        for k in range(n):
            if (last >> k) & 1 == 0:  # 如果last状态中没有访问过景点k，跳过
                continue
            if dp[k][last] == 10 ** 9:  # 如果last状态下景点k不可达，跳过
                continue
            # 更新dp[j][i]为从状态last到达j的最小公交次数
            dp[j][i] = min(dp[j][i], dp[k][last] + dist[k][j])

# 最终答案，遍历所有景点，在访问所有景点的状态（state - 1）下找到最小公交次数
ans = 10 ** 9
for i in range(n):
    ans = min(ans, dp[i][state - 1])

# 输出结果，如果ans仍然是初始值，说明无法访问所有景点，输出0，否则输出ans
if ans == 10 ** 9:
    print(0)
else:
    print(ans)

cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

int main() {
    // 读取景点数量
    int n;
    cin >> n;

    // 读取公交路线的二维数组
    vector<vector<int>> edge(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> edge[i][j];
        }
    }

    // 初始化距离数组dist，初始值设为一个很大的数（INT_MAX），表示不可达
    vector<vector<int>> dist(n, vector<int>(n, INT_MAX));
    for (int i = 0; i < n; i++) {
        dist[i][i] = 0;
    }

    // 根据输入的公交线路设置初始直达距离
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (edge[i][j] == 1) {
                dist[i][j] = 1;
            }
        }
    }

    // 使用Floyd-Warshall算法计算所有景点之间的最短路径
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX) {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }

    // 使用状态压缩DP来记录到达每个状态时的最少公交次数
    int state = 1 << n;
    vector<vector<int>> dp(n, vector<int>(state, INT_MAX));

    // 初始化DP状态，每个景点作为起点时的状态
    for (int i = 0; i < n; i++) {
        dp[i][1 << i] = 0;
    }

    // 遍历所有可能的状态i（从1到2^n-1）
    for (int i = 1; i < state; i++) {
        for (int j = 0; j < n; j++) {
            if ((i & (1 << j)) == 0) continue;
            int last = i ^ (1 << j);
            for (int k = 0; k < n; k++) {
                if ((last & (1 << k)) == 0 || dp[k][last] == INT_MAX || dist[k][j] == INT_MAX) continue;
                dp[j][i] = min(dp[j][i], dp[k][last] + dist[k][j]);
            }
        }
    }

    // 最终答案，遍历所有景点，在访问所有景点的状态（state - 1）下找到最小公交次数
    int ans = INT_MAX;
    for (int i = 0; i < n; i++) {
        ans = min(ans, dp[i][state - 1]);
    }

    // 输出结果，如果ans仍然是初始值，说明无法访问所有景点，输出0，否则输出ans
    if (ans == INT_MAX) {
        cout << 0 << endl;
    } else {
        cout << ans << endl;
    }

    return 0;
}

OJ会员可以通过点击题目上方《已通过》查看其他通过代码来学习。

题目内容

春节将近，小明想在节日期间逛一逛城里的 $N$ 个著名景点，正好所有的景点都能通过坐公交到达，请帮小明设计一下，怎么搭乘公交路线才能最快逛完所有的景点。

1、景点编号 $0,1,2,…,N-1$

2、用数组 $arr[N] [N]$表示景点和景点之间是否有直达公交路线相连

3、$arr[i] [j]=1$ 表示景点 $i$ 和景点 $j$ 之间有直达公交相连，$arr[i] [j] =0$ 表示没有

4、公交可以双向行驶，即如果 $arr[i] [j]=1$，则必然 $arr[i] [j]=1$

5、每个景点可以经过多次，两个景点的公交也可以坐多次

6、可以从任一景点开始游玩

输入描述

第一行:景点数量 $N(0<N<=20)$

后续 $N$ 行: $N$ 个元素表示景点与景点之间的公交到达关系

输出描述

最少乘坐公交的次数(如果不能逛完所有景点，则输出 $0$ )

样例1

输入

5
0 1 0 1 0
1 0 1 0 0
0 1 0 0 0
1 0 0 0 1
0 0 0 1 0

输出

4

说明

样例2

输入

6
0 1 1 0 0 0
1 0 0 0 0 0
1 0 0 1 1 0
0 0 1 0 0 0
0 0 1 0 0 1
0 0 0 0 1 0

输出

6

说明