AcWing 731. 毕业旅行问题
宋标 Lv5
  2022-08-18 02:31:05 2022-08-18 02:31    

题目

小明目前在做一份毕业旅行的规划。

打算从北京出发，分别去若干个城市，然后再回到北京，每个城市之间均乘坐高铁，且每个城市只去一次。

由于经费有限，希望能够通过合理的路线安排尽可能的省些路上的花销。

给定一组城市和每对城市之间的火车票的价钱，找到每个城市只访问一次并返回起点的最小车费花销。

注意：北京为 号城市。

输入格式

城市个数 。

城市间的车票价钱 行 列的矩阵 。

输出格式

输出一个整数，表示最小车费花销。

数据范围

,包括北京
车票价格均不超过 元。

输入样例：

4
0 2 6 5
2 0 4 4
6 4 0 2
5 4 2 0

输出样例：

13

说明

共 个城市，城市 和城市 的车费为 ，城市 和城市 之间的车费为 ，城市 和城市 之间的车费为 ，城市 和城市 之间的车费为 ，以此类推。

假设任意两个城市之间均有单程票可买，且价格均在 元以内，无需考虑极端情况。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <cstring>
#define N 20

using namespace std;

int n;
int w[N][N];
int f[1 << N][N];

int main()
{
    ios::sync_with_stdio(false);
    cin >> n;

    for (int i = 0; i < n; ++ i)
        for (int j = 0; j < n; ++ j)
            cin >> w[i][j];

    memset(f, 0x3f, sizeof f);
    f[1][0] = 0;

    for (int i = 1; i < 1 << n; i += 2)
        for (int j = 0; j < n; ++ j)
            if (i >> j & 1)
                for (int k = 0; k < n; ++ k)
                    if (i ^ (1 << j) >> k & 1)
                        f[i][j] = min(f[i][j], f[i ^ (1 << j)][k] + w[k][j]);


    int ans = 0x3f3f3f3f;
    for (int i = 1; i < n; ++ i) ans = min(ans, f[(1 << n) - 1][i] + w[i][0]);

    cout << ans << endl;

    return 0;
}
 评论