题解 | 毕业旅行问题

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

int main() {
    int n;
    cin >> n;
    
    // 读取城市间的车票价钱矩阵
    vector<vector<int>> costs(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> costs[i][j];
        }
    }
    
    // dp[state][city]表示当前在city，已访问城市状态为state的最小花费
    vector<vector<int>> dp(1 << n, vector<int>(n, INT_MAX));
    dp[1][0] = 0;  // 初始状态：只访问过起点
    
    // 遍历所有可能的状态
    for (int state = 1; state < (1 << n); state++) {
        for (int curr = 0; curr < n; curr++) {
            if (!(state & (1 << curr))) continue;
            
            // 尝试访问下一个城市
            for (int next = 0; next < n; next++) {
                if (state & (1 << next)) continue;
                
                int next_state = state | (1 << next);
                if (dp[state][curr] != INT_MAX) {
                    dp[next_state][next] = min(
                        dp[next_state][next],
                        dp[state][curr] + costs[curr][next]
                    );
                }
            }
        }
    }
    
    // 计算返回起点的最小花费
    int final_state = (1 << n) - 1;
    int result = INT_MAX;
    for (int last = 1; last < n; last++) {
        if (dp[final_state][last] != INT_MAX) {
            result = min(result, dp[final_state][last] + costs[last][0]);
        }
    }
    
    cout << result << endl;
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        // 读取城市间的车票价钱矩阵
        int[][] costs = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                costs[i][j] = sc.nextInt();
            }
        }
        
        // dp[state][city]表示当前在city，已访问城市状态为state的最小花费
        int[][] dp = new int[1 << n][n];
        for (int[] row : dp) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }
        dp[1][0] = 0;  // 初始状态：只访问过起点
        
        // 遍历所有可能的状态
        for (int state = 1; state < (1 << n); state++) {
            for (int curr = 0; curr < n; curr++) {
                if ((state & (1 << curr)) == 0) continue;
                
                // 尝试访问下一个城市
                for (int next = 0; next < n; next++) {
                    if ((state & (1 << next)) != 0) continue;
                    
                    int nextState = state | (1 << next);
                    if (dp[state][curr] != Integer.MAX_VALUE) {
                        dp[nextState][next] = Math.min(
                            dp[nextState][next],
                            dp[state][curr] + costs[curr][next]
                        );
                    }
                }
            }
        }
        
        // 计算返回起点的最小花费
        int finalState = (1 << n) - 1;
        int result = Integer.MAX_VALUE;
        for (int last = 1; last < n; last++) {
            if (dp[finalState][last] != Integer.MAX_VALUE) {
                result = Math.min(result, dp[finalState][last] + costs[last][0]);
            }
        }
        
        System.out.println(result);
        sc.close();
    }
}

def solve():
    n = int(input())
    
    # 读取城市间的车票价钱矩阵
    costs = []
    for _ in range(n):
        costs.append(list(map(int, input().split())))
    
    # dp[state][city]表示当前在city，已访问城市状态为state的最小花费
    dp = [[float('inf')] * n for _ in range(1 << n)]
    dp[1][0] = 0  # 初始状态：只访问过起点
    
    # 遍历所有可能的状态
    for state in range(1, 1 << n):
        for curr in range(n):  # 当前所在城市
            if not (state & (1 << curr)):  # 当前状态未包含该城市
                continue
                
            # 尝试访问下一个未访问的城市
            for next_city in range(n):
                if state & (1 << next_city):  # 已访问过，跳过
                    continue
                
                # 更新到达next_city的最小花费
                next_state = state | (1 << next_city)
                dp[next_state][next_city] = min(
                    dp[next_state][next_city],
                    dp[state][curr] + costs[curr][next_city]
                )
    
    # 计算所有城市都访问后，从最后一个城市返回起点的最小花费
    final_state = (1 << n) - 1
    result = float('inf')
    for last_city in range(1, n):
        result = min(result, dp[final_state][last_city] + costs[last_city][0])
        
    print(result)

if __name__ == "__main__":
    solve()