题解 | 郊区春游

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

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int R = in.nextInt();
        int[] S = new int[R];
        for (int i = 0; i < R; i++) {
            S[i] = in.nextInt();
        }

        // 初始化距离矩阵
        int[][] dist = new int[n + 1][n + 1];
        int INF = 1_000_000_000;
        for (int i = 1; i <= n; i++) {
            Arrays.fill(dist[i], INF);
            dist[i][i] = 0;
        }
        for (int i = 0; i < m; i++) {
            int a = in.nextInt();
            int b = in.nextInt();
            int c = in.nextInt();
            if (dist[a][b] > c) {
                dist[a][b] = c;
                dist[b][a] = c;
            }
        }

        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }

        int[][] cost = new int[R][R];
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < R; j++) {
                cost[i][j] = dist[S[i]][S[j]];
            }
        }

        int[][] dp = new int[1 << R][R];
        for (int[] row : dp) {
            Arrays.fill(row, INF);
        }
        for (int i = 0; i < R; i++) {
            dp[1 << i][i] = 0;
        }

        for (int mask = 0; mask < (1 << R); mask++) {
            for (int u = 0; u < R; u++) {
                if ((mask & (1 << u)) == 0) continue;
                for (int v = 0; v < R; v++) {
                    if ((mask & (1 << v)) != 0) continue;
                    int newMask = mask | (1 << v);
                    if (dp[newMask][v] > dp[mask][u] + cost[u][v]) {
                        dp[newMask][v] = dp[mask][u] + cost[u][v];
                    }
                }
            }
        }

        int fullMask = (1 << R) - 1;
        int res = INF;
        for (int u = 0; u < R; u++) {
            if (dp[fullMask][u] < res) {
                res = dp[fullMask][u];
            }
        }
        System.out.println(res);
    }
}

https://www.nowcoder.com/discuss/727521113110073344

思路：

1. 输入处理：读取输入的郊区数、道路数和目标郊区数，以及目标郊区的编号。
2. Floyd-Warshall算法：计算所有郊区之间的最短路径，构建距离矩阵。
3. 代价矩阵构建：根据预处理的最短路径结果，构建目标郊区之间的代价矩阵。
4. 动态规划初始化：初始化动态规划数组，处理每个目标郊区作为起点的情况。
5. 状态转移：遍历所有状态，更新每个状态的最小花费。
6. 结果输出：找到访问所有目标郊区的最小总花费并输出。