最优哈密顿路径

题目描述

有 'n' ('n'≤17) 座城市，用 1 到 'n' 的整数编号。城市两两之间都有道路连接，经过每条道路需要支付一定的费用。

请问从 1 号城市出发，经过每个城市'恰好'一次，且最后不回到 1 号城市所支付的总费用最小是多少。

输入格式

输入的第一行包含一个正整数 'n'，表示城市的数量。

接下来 'n' 行，每行包含 'n' 个非负整数。其中的第 'i' 行第 'j' 个数表示城市 'i' 和 'j' 之间道路需要支付的费用。保证第 'i' 行第 'j' 个数和第 'j' 行第 'i' 个数相等。因为城市到自己没有道路，因此第 'i' 行第 'i' 个数没有意义，为了统一，我们保证这个数为 0。

保证每条道路的费用都是不超过 10000 的正整数，数据可以视为独立等概率在取值范围内'随机取得'。

输出格式

输出一个整数，表示经过每个城市恰好一次所需要的最小费用。

样例 #1

样例输入 #1

3
0 4632 1445
4632 0 9759
1445 9759 0

样例输出 #1

11204

样例 #2

样例输入 #2

5
0 3173 9092 3168 8129
3173 0 9689 5125 1544
9092 9689 0 4512 2406
3168 5125 4512 0 4965
8129 1544 2406 4965 0

样例输出 #2

11630

提示

共有 10 个测试点，第 'i' 个测试点对应 'n' = 'i'+7。

写出一个正确的C++代码内容：```cpp #include #include #include using namespace std;

const int INF = 1e9;

int main() { int n; cin >> n; vector<vector> graph(n, vector(n)); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> graph[i][j]; } }

// dp[mask][i]表示从起点出发，经过mask中的城市，最后到达城市i的最小费用
vector<vector<int>> dp(1 << n, vector<int>(n, INF));
dp[1][0] = 0; // 起点为城市0，mask为1表示只经过城市0

for (int mask = 1; mask < (1 << n); mask++) {
    for (int i = 0; i < n; i++) {
        if ((mask >> i) & 1) { // mask中包含城市i
            for (int j = 0; j < n; j++) {
                if (((mask ^ (1 << i)) >> j) & 1) { // mask中除城市i外，还包含城市j
                    dp[mask][i] = min(dp[mask][i], dp[mask ^ (1 << i)][j] + graph[j][i]);
                }
            }
        }
    }
}

int minCost = INF;
for (int i = 0; i < n; i++) {
    minCost = min(minCost, dp[(1 << n) - 1][i] + graph[i][0]);
}

cout << minCost << endl;

return 0;

}