思路

这是一个带有方向性和可能缺失路径的旅行商问题（TSP，Traveling Salesman Problem）的变种。主要目标是找到一条起点和终点都在入口，经过所有景点至少一次的最短路径。由于允许多次经过同一个景点或返回入口，问题的复杂度有所增加。

主要步骤如下：

1. 预处理最短路径：

   • 使用 Floyd 算法计算所有景点之间的最短路径，填补直接路径不存在的情况。这一步确保即使某些景点之间没有直接通路，也能通过其他景点间接到达。

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

(1). 状态定义：

• 位掩码表示：对于 $N$ 个景点，可以用一个 $N$ 位的二进制数来表示已访问的景点集合。具体来说，第 $i$ 位（从 $0$ 开始）为 1 表示景点 $i+1$ 已被访问，0 表示未被访问。
• DP 状态：dp[mask][u] 表示在已经访问了 mask 集合的景点后，当前位于景点 $u$ 时的最小耗时。
  • mask：一个整数，二进制形式表示已访问的景点集合。
  • u：当前所在的景点编号（包括入口 $0$）。

(2). 初始状态：

• dp[0][0] = 0：表示一开始在入口且未访问任何景点，耗时为 $0$。
• 其他状态初始化为 INF，表示尚未计算或不可达。

(3). 状态转移：

• 遍历所有可能的 mask：
  • 从 0 到 (1 << N) - 1，即所有可能的景点访问状态。
• 对于每个 mask，遍历所有可能的当前所在景点 u：
  • 如果 dp[mask][u] 已被计算（即不为 INF），则尝试从 u 移动到其他景点 v。
• 尝试移动到每个未被访问的景点 v：
  • 检查景点 v 是否已在 mask 中：
    • 如果未被访问，则更新新的 mask 为 mask | (1 << (v-1))。
    • 计算新的耗时：dp[new_mask][v] = min(dp[new_mask][v], dp[mask][u] + G[u][v])，其中 G[u][v] 是从 u 到 v 的最短耗时。
• 允许重复访问：
  • 虽然问题允许重复访问景点，但在 DP 转移中，只需考虑首次访问未访问的景点 v，因为重复访问不会带来新的状态，只会增加耗时，不会有助于找到最优解。

(4). 最终结果：

• 所有景点被访问后的状态：mask = (1 << N) - 1。
• 从所有可能的终点 u 回到入口 $0$：
  • 计算 dp[all_visited][u] + G[u][0]，即从终点 u 返回入口的总耗时。
• 选择最小的总耗时 作为最终结果。

cpp

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;

int main(){
    int N;
    cin >> N;
    // 初始化距离矩阵
    vector<vector<int>> G(N+1, vector<int>(N+1, INF));
    for(int i=0;i<=N;i++){
        for(int j=0;j<=N;j++){
            int val;
            cin >> val;
            if(val == -1){
                G[i][j] = INF;
            }
            else{
                G[i][j] = val;
            }
        }
    }
    // Floyd-Warshall 计算所有点之间的最短路径
    for(int k=0;k<=N;k++){
        for(int i=0;i<=N;i++){
            for(int j=0;j<=N;j++){
                if(G[i][k] < INF && G[k][j] < INF){
                    G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
                }
            }
        }
    }
    int size = 1 << N; // N个景点
    // 初始化 DP 数组，设为 INF
    // dp[mask][u] 表示访问了 mask 集合的景点，当前在景点 u 的最小耗时
    vector<vector<int>> dp(size, vector<int>(N+1, INF));
    dp[0][0] = 0; // 从入口出发，未访问任何景点
    // 遍历所有状态
    for(int mask=0; mask < size; mask++){
        for(int u=0; u<=N; u++){
            if(dp[mask][u] < INF){
                // 尝试前往每一个景点，包括入口
                for(int v=0; v<=N; v++){
                    if(v == 0){
                        // 前往入口，不改变 mask
                        if(G[u][v] < INF){
                            dp[mask][v] = min(dp[mask][v], dp[mask][u] + G[u][v]);
                        }
                    }
                    else{
                        int bit = v-1;
                        if(!(mask & (1 << bit))){ // 如果景点v未被访问
                            if(G[u][v] < INF){
                                int next_mask = mask | (1 << bit);
                                dp[next_mask][v] = min(dp[next_mask][v], dp[mask][u] + G[u][v]);
                            }
                        }
                        else{
                            // 景点v已访问，仍可前往（允许重复经过）
                            if(G[u][v] < INF){
                                dp[mask][v] = min(dp[mask][v], dp[mask][u] + G[u][v]);
                            }
                        }
                    }
                }
            }
        }
    }
    // 最终需要访问所有景点，并回到入口
    int final_mask = (1 << N) -1;
    int res = INF;
    for(int u=0; u<=N; u++){
        if(dp[final_mask][u] < INF && G[u][0] < INF){
            res = min(res, dp[final_mask][u] + G[u][0]);
        }
    }
    cout << res;
    return 0;
}

python

import sys
import math

def main():
    import sys
    sys.setrecursionlimit(1 << 25)
    N = int(sys.stdin.readline())
    INF = math.inf
    G = []
    for _ in range(N+1):
        row = list(map(int, sys.stdin.readline().split()))
        new_row = []
        for val in row:
            if val == -1:
                new_row.append(INF)
            else:
                new_row.append(val)
        G.append(new_row)
    # Floyd-Warshall 算法
    for k in range(N+1):
        for i in range(N+1):
            for j in range(N+1):
                if G[i][k] != INF and G[k][j] != INF:
                    if G[i][j] > G[i][k] + G[k][j]:
                        G[i][j] = G[i][k] + G[k][j]
    size = 1 << N
    # 初始化 DP 数组，设为 INF
    # dp[mask][u] 表示访问了 mask 集合的景点，当前在景点 u 的最小耗时
    dp = [ [INF]*(N+1) for _ in range(size) ]
    dp[0][0] = 0
    # 遍历所有状态
    for mask in range(size):
        for u in range(N+1):
            if dp[mask][u] < INF:
                # 尝试前往每一个景点，包括入口
                for v in range(N+1):
                    if v ==0:
                        # 前往入口，不改变 mask
                        if G[u][v] < INF:
                            if dp[mask][v] > dp[mask][u] + G[u][v]:
                                dp[mask][v] = dp[mask][u] + G[u][v]
                    else:
                        bit = v-1
                        if not (mask & (1 << bit)):
                            # 景点v未被访问
                            if G[u][v] < INF:
                                next_mask = mask | (1 << bit)
                                if dp[next_mask][v] > dp[mask][u] + G[u][v]:
                                    dp[next_mask][v] = dp[mask][u] + G[u][v]
                        else:
                            # 景点v已被访问，允许重复经过
                            if G[u][v] < INF:
                                if dp[mask][v] > dp[mask][u] + G[u][v]:
                                    dp[mask][v] = dp[mask][u] + G[u][v]
    # 最终需要访问所有景点，并回到入口
    final_mask = (1 << N) -1
    res = INF
    for u in range(N+1):
        if dp[final_mask][u] < INF and G[u][0] < INF:
            res = min(res, dp[final_mask][u] + G[u][0])
    print(int(res))

if __name__ == "__main__":
    main()

java

import java.util.*;
import java.io.*;

public class Main {
    static final int INF = 1000000000;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[][] G = new int[N + 1][N + 1];
        for (int i = 0; i <= N; i++) {
            String[] parts = br.readLine().split(" ");
            for (int j = 0; j <= N; j++) {
                int val = Integer.parseInt(parts[j]);
                if (val == -1) {
                    G[i][j] = INF;
                } else {
                    G[i][j] = val;
                }
            }
        }

        // Floyd-Warshall 算法计算所有点之间的最短路径
        for (int k = 0; k <= N; k++) {
            for (int i = 0; i <= N; i++) {
                for (int j = 0; j <= N; j++) {
                    if (G[i][k] < INF && G[k][j] < INF) {
                        G[i][j] = Math.min(G[i][j], G[i][k] + G[k][j]);
                    }
                }
            }
        }

        int size = 1 << N;
        int[][] dp = new int[size][N + 1];
        for (int i = 0; i < size; i++) {
            Arrays.fill(dp[i], INF);
        }
        dp[0][0] = 0; // 从入口出发，未访问任何景点

        // 遍历所有状态
        for (int mask = 0; mask < size; mask++) {
            for (int u = 0; u <= N; u++) {
                if (dp[mask][u] < INF) {
                    // 尝试前往每一个景点，包括入口
                    for (int v = 0; v <= N; v++) {
                        if (v == 0) {
                            // 前往入口，不改变 mask
                            if (G[u][v] < INF) {
                                dp[mask][v] = Math.min(dp[mask][v], dp[mask][u] + G[u][v]);
                            }
                        } else {
                            int bit = v - 1;
                            if ((mask & (1 << bit)) == 0) {
                                // 景点 v 未被访问
                                if (G[u][v] < INF) {
                                    int next_mask = mask | (1 << bit);
                                    dp[next_mask][v] = Math.min(dp[next_mask][v], dp[mask][u] + G[u][v]);
                                }
                            } else {
                                // 景点 v 已被访问，允许重复经过
                                if (G[u][v] < INF) {
                                    dp[mask][v] = Math.min(dp[mask][v], dp[mask][u] + G[u][v]);
                                }
                            }
                        }
                    }
                }
            }
        }

        // 最终需要访问所有景点，并回到入口
        int final_mask = (1 << N) - 1;
        int res = INF;
        for (int u = 0; u <= N; u++) {
            if (dp[final_mask][u] < INF && G[u][0] < INF) {
                res = Math.min(res, dp[final_mask][u] + G[u][0]);
            }
        }
        System.out.println(res);
    }
}

题目内容

小明计划到某网红旅游景区来一次“特种兵”旅游，景区有 $N$ 个最点,请帮助小明规划一条游览路径，使得游览完所有景点花费的时间最短,以便于安排返程时间。

输入描述

第一行，景点数量 $N$ 。

接下来的 $N+1$ 行，每行 $N+1$ 个整数，以空格分隔，构成一个 $N+1*N+1$ 的矩阵。其中，坐标 $0$ 表示景区入口，$G[0] [j]$ 表示从景区入口到景区 $j$ 路程的耗时，$G[j] [0]$ 表示从景区 $j$ 到景区入口路程的耗时，$G [i] [j]$ 表示从景区 $i$ 到景点 $j$ 路程的耗时。

由于景区的道路不总是平坦的，景点间往返路程上花费的时间可能不同。如果 $i=j$，$G [i] [j] =0$ ；如果景点 $i$ 与景点 $j$ 之间没有直接相通的道路，则 $G [i] [j]=G [j] [i] = -1$；从景区入口，一定可以到达每一个景点(直达或者经过其它景点)。

• $1 <= N <= 15$

• 从景区入口出发，可以到达所有景点，要么是直达，要么是经过其它景点

• 在游览路径中，可以重复经过任一景点

输出描述

游览完所有景点在路途上花费的最短时间。

样例1

输入

2
0 2 3
1 0 5
2 2 0

输出

6

说明

如图所示， 游览路径: 景区入口>景点 $2$ ->景点 $1$ ->景区入口，耗时 $3+2+1=6$ 最少。

样例2

输入

3
0 1 2 -1
3 0 5 2
2 2 0 3
-1 2 4 0

输出

9

说明

如图所示，游览路径:景区入口->景点 $1$ ->景点 $3$ ->景点 $2$ ->景区入口，耗时 $1+2+4+2=9$ 最少。

样例3

输入

3
0 1 3 1
2 0 -1 -1
1 -1 0 4
1 -1 5 0

输出

9

说明

如图所示，游览路径:景区入口>景点 $1$ -> 景区入口 -> 景点 $2$ ->景区入口->景点 $3$ ->景区入口，耗时$1+2+3+1+1+1=9$ 最少。