状压dp1

题解

package com.zhang.reflection.面试.算法模版.动态规划;
import java.io.*;
import java.util.*;
/**
 * 描述
 * 今天春天铁子的班上组织了一场春游，在铁子的城市里有n个郊区和m条无向道路，第i条道路连接郊区Ai和Bi，路费是Ci。
 * 经过铁子和顺溜的提议，他们决定去其中的R个郊区玩耍（不考虑玩耍的顺序），但是由于他们的班费紧张，所以需要找到一条旅游路线使得他们的花费最少，假设他们制定的旅游路线为V1, V2 ,V3 ... VR，那么他们的总花费为从V1到V2的花费加上V2到V3的花费依次类推，注意从铁子班上到V1的花费和从VR到铁子班上的花费是不需要考虑的，因为这两段花费由学校报销而且我们也不打算告诉你铁子学校的位置。
 * 输入描述：
 * 第一行三个整数n, m, R(2 ≤ n ≤ 200, 1 ≤ m ≤ 5000, 2 ≤ R ≤ min(n, 15))。
 * 第二行R个整数表示需要去玩耍的郊区编号。
 * 以下m行每行Ai, Bi, Ci(1 ≤ Ai, Bi ≤ n, Ai ≠ Bi, Ci ≤ 10000)
 * 保证不存在重边。
 *
 * 4 6 3
 * 2 3 4
 * 1 2 4
 * 2 3 3
 * 4 3 1
 * 1 4 1
 * 4 2 2
 * 3 1 6
 *
 * 3
 */
public class 状压dp1 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] arr = br.readLine().split(" ");
        //n个郊区
        int n = Integer.parseInt(arr[0]);
        //m条通路
        int m = Integer.parseInt(arr[1]);
        //去R个郊区
        int r = Integer.parseInt(arr[2]);

        arr = br.readLine().split(" ");
        //去这几个郊区玩
        int[] go = new int[r];
        for (int i = 0; i < r; i++) {
            go[i] = Integer.parseInt(arr[i]);
        }

        //init matrix matrix[i][j]表示i到j的最短路径
        int[][] matrix = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            //相加超出int了
//            Arrays.fill(matrix[i], Integer.MAX_VALUE);
            Arrays.fill(matrix[i], 1000000000);
            matrix[i][i] = 0;
        }

        int a, b, cost;
        for (int i = 0; i < m; i++) {
            arr = br.readLine().split(" ");
            //相连的郊区及花费
            a = Integer.parseInt(arr[0]);
            b = Integer.parseInt(arr[1]);
            cost = Integer.parseInt(arr[2]);
//            matrix[a][b] = Math.min(matrix[a][b], cost);
//            matrix[b][a] = matrix[a][b];
            matrix[a][b] = cost;
            matrix[b][a] = cost;
        }

        //floyd算法 求两点间最小距离
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                for (int k = 1; k <= n; k++) {
                    matrix[j][k] = Math.min(matrix[j][k], matrix[j][i] + matrix[i][k]);
                }
            }
        }

        //init dp
        int t = 1 << r;
        int[][] dp = new int[t][r];
        for (int i = 0; i < t; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        for (int i = 0; i < r; i++) {
            dp[1 << i][i] = 0;
        }

        //枚举i，j，k。状态转移
        for (int i = 1; i < t ; i++) {
            for (int j = 0; j < r; j++) {
                if ((i & (1 << j)) > 0) {
                    for (int k = 0; k < r; k++) {
                        if ((i & (1 << k)) == 0) {
                            dp[i + (1 << k)][k] = Math.min(dp[i + (1 << k)][k], dp[i][j] + matrix[go[j]][go[k]]);
                        }
                    }
                }
            }
        }

        //取最小值
        int ans = Integer.MAX_VALUE;
        for(int i = 0; i < r; i++) {
            ans = Math.min(ans, dp[t - 1][i]);
        }
        System.out.println(ans);
    }
}