售货员的难题

题目背景

数据有更改

题目描述

某乡有 $n\ (2\le n\le 20)$ 个村庄，有一个售货员，他要到各个村庄去售货，各村庄之间的路程 $s\ (0<s<1000)$ 是已知的，且 $A$ 村到 $B$ 村与 $B$ 村到 $A$ 村的路大多不同。为了提高效率，他从商店出发到每个村庄一次，然后返回商店所在的村，假设商店所在的村庄为 $1$，他不知道选择什么样的路线才能使所走的路程最短。请你帮他选择一条最短的路。

输入格式

村庄数 $n$ 和各村之间的路程（均是整数）。

第一行，第 $i+1$ 行第 $j$ 个数代表村庄 $i$ 到 $j$ 的单向路径的路程。

输出格式

最短的路程。

样例 #1

样例输入 #1

3
0 2 1
1 0 2
2 1 0

样例输出 #1

3

题解

这个问题是一个经典的旅行商问题（TSP），我们需要找到一条从商店（村庄1）出发，访问所有村庄一次，然后返回商店的最短路径。

我们的解决方案是使用一个二维DP数组f，其中f[i][j]表示当前状态为i，当前访问的村庄为j的最短路径长度。状态i是一个二进制数，其中的每一位表示一个村庄是否已经被访问过。

首先，我们设置f[1][1] = 0，表示从村庄1出发，只访问村庄1的路径长度为0。

状态转移方程大致如下

f[i][j] = min(f[i][j] , f[能到 j 的上一个节点k的状态][k] + f[k][j])

最后，我们遍历所有的村庄，找到从所有村庄返回商店的最短路径长度，这就是我们要找的最短路径长度。

C++代码

不是，luogu的 java 又 MLE 了

#include <iostream>
#include <cstring>
using namespace std;

const int maxn = 25;
int n;
int a[maxn][maxn];
int f[1 << 20][maxn]; // 状态是 i，当前访问到 j 节点的最小值

void print(int i)
{
    while (i != 0)
    {
        cout << (i & 1);
        i >>= 1;
    }
    cout << '\n';
}

signed main()
{
    memset(f, 0x3f3f, sizeof(f));
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            cin >> a[i][j];
        }
    }

    f[1][1] = 0;
    for (int k = 1; k <= (1 << n) - 1; k++)
        for (int i = 1; i <= n; i++)
        {
            if ((1 << (i - 1)) & !k) // 当前状态该点未访问过
                continue;
            for (int j = 1; j <= n; j++)
            {
                if (i == j)
                    continue;
                int last = (1 << (i - 1)) ^ k; // 上一个状态是什么
                if (f[last][j] + a[j][i] < f[k][i])
                {
                    f[k][i] = f[last][j] + a[j][i];
                }
            }
        }

    int min_ans = 0x3f3f;
    for (int i = 1; i <= n; i++)
        min_ans = min(min_ans, f[(1 << n) - 1][i] + a[i][1]);
    cout << min_ans << endl;
    return 0;
}

END