P1171 售货员的难题 · 习题解析｜信息学奥赛算法练功房

0题目原文（本地存了一份）

为什么要在这儿抄一份题面

原题在洛谷上（页头有链接）。别人的网站不归我们管，打不开、改版、题号调整都可能发生。所以每个解析页都把题面转录一份存在本地，跟着仓库一起进版本库。

转录自洛谷 P1171，日期见页头。两边不一致时信原站。

题目背景

数据有更改

题目描述

某乡有 n 个村庄，有一个售货员，他要到各个村庄去售货，各村庄之间的路程 s(i,j) 是已知的，且 A 村到 B 村与 B 村到 A 村的路大多不同。

为了提高效率，他从商店出发到每个村庄一次，然后返回商店所在的村，假设商店所在的村庄为 1，他不知道选择什么样的路线才能使所走的路程最短。请你帮他选择一条最短的路。

输入格式

第一行是一个整数，表示村庄数 n。

接下来 n 行，每行 n 个整数，第 i 行的第 j 个整数表示 i 到 j 的单向路径的距离 s(i,j)。

输出格式

一行一个整数表示最短的路程。

说明/提示

对全部的测试数据，保证 2 ≤ n ≤ 20，1 ≤ s(i,j) < 10³。

输入输出样例

输入

输出

三个村庄。走 1 → 3 → 2 → 1：1 + 1 + 1 = 3。

⚠ n = 3 意味着只有两条回路可选 —— 所以这组样例只挡住了四个错法里的一个 （「忘了回起点」打出 2）。贪心、转置、取 min 三个都原样打出 3。

1★ 第一版：每次去最近的那个村（最近邻贪心）

p1171Greedy.cpp✗ 第一版：最近邻贪心

// ✗ P1171 第一版：最近邻贪心（每次去「还没去过的里最近的那个」）
//
// 这是几乎所有人对 TSP 的第一反应，也是它最著名的陷阱：
// ★ 它给出的是**一条真走得通的回路** ⇒ 它的路程**恒 ≥ 最优**，永远不会少报。
// 错在哪：为了眼前省一点，可能被逼着在最后走一条极长的边回来。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n) || n <= 0) return 0;
    vector<vector<int>> d(n, vector<int>(n));
    for (auto& row : d) for (auto& x : row) cin >> x;
    if (n == 1) { cout << 0 << '\n'; return 0; }

    vector<char> vis(n, 0);
    vis[0] = 1;
    long long sum = 0;
    int cur = 0;
    for (int t = 1; t < n; t++) {
        int best = -1;
        for (int j = 0; j < n; j++)
            if (!vis[j] && (best < 0 || d[cur][j] < d[cur][best])) best = j;
        sum += d[cur][best];
        vis[best] = 1;
        cur = best;
    }
    sum += d[cur][0];
    cout << sum << '\n';
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

★★ 它恒 ≥ 正解 —— 而这道题的贪心错得比前几章都狠

它排出来的是一条真走得通的回路 ⇒ 它的路程恒 ≥ 最优，永远不会少报。


它 ≥ 正解	★ 300 / 300
300 轮被抓	285
错的时候平均多走	★ 56.40%
最多多走	★ 182.38%

⇒ 对照第 20 章 P1048 的性价比贪心（错时只差 10.96%）、第 26 章 P1220（48.67%）：同样叫贪心，错的幅度能差一个数量级 —— 而 TSP 是错得最难看的那一头（为了眼前省一点，最后被逼着走一条极长的边回来）。

2★★ 正解：状压 DP —— 而这道题就是本章的模板题

★ f[S][i] = 走过的集合是 S、此刻停在 i

    f[S][i] = 已经走过的村庄集合恰好是 S（且 i ∈ S），此刻人停在 i，
              从 1 号村出发走到这里的最短路程

    f[S | 1<<j][j] = min(f[S][i] + d[i][j])        j ∉ S
    答案 = min over i≠0 of f[全集][i] + d[i][0]     ★ 最后要回起点

推导、填表顺序（S 自然顺序就够，因为 S | (1<<j) 一定比 S 大）、以及另外六种错法，第 28 章正文里都有 —— 这道题是那一章的原题，写完直接交，一遍就该过。这一页只补正文没量过的那几件事。

p1171.cpp★ 这一版就能 AC

// P1171 售货员的难题 —— 正解：状压 DP（TSP 模板），O(2ⁿ × n²)
//
//   f[S][i] = 已经走过的村庄集合恰好是 S（且 i ∈ S），此刻人停在 i，
//             从 1 号村出发走到这里的最短路程。
//   转移    f[S | 1<<j][j] = min(f[S][i] + d[i][j])      j ∉ S
//   答案    min over i≠0 of f[全集][i] + d[i][0]         ★ 最后要**回起点**
//
// 推导、填表顺序、以及另外六种错法，[第 28 章正文](/ch/28-bitmask-dp/) 里都有，这一页不重复。
//
// ⚠ 这道题和正文那份模板只差一件事：**它的图是有向的**（题面明写「A 村到 B 村与
//    B 村到 A 村的路大多不同」）—— 所以 d[i][j] 和 d[j][i] 不能混用。
//    正文那份本来就没假设对称，直接交就能过。
//
// ⚠ 顶格 n = 20：状态数 2²⁰ × 20 = 2 千万个 long long = 168 MB，而题面给了 512 MB。
//    ★ 但这一步值得算一遍再写 —— 见 p1171Count.cpp 第 ⑤ 段。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n) || n <= 0) return 0;
    vector<vector<int>> d(n, vector<int>(n));
    for (auto& row : d) for (auto& x : row) cin >> x;
    if (n == 1) { cout << 0 << '\n'; return 0; }

    const int INF = INT_MAX / 4;
    int full = (1 << n) - 1;
    vector<vector<int>> f(1 << n, vector<int>(n, INF));
    f[1][0] = 0;                                    // 出发：只去过 1 号村（下标 0），人在那儿

    for (int S = 0; S <= full; S++)                 // ★ 自然顺序：S | (1<<j) 一定比 S 大
        for (int i = 0; i < n; i++) {
            if (f[S][i] >= INF) continue;
            if (!(S >> i & 1)) continue;
            for (int j = 0; j < n; j++) {
                if (S >> j & 1) continue;
                int& t = f[S | 1 << j][j];
                t = min(t, f[S][i] + d[i][j]);
            }
        }

    int ans = INF;
    for (int i = 1; i < n; i++)
        if (f[full][i] < INF) ans = min(ans, f[full][i] + d[i][0]);   // ★ 加回起点
    cout << ans << '\n';
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

3⚠⚠ 第二个「错法」根本不是错法 —— 而它同时称出了题面那句话的分量

题面特意写着「A 村到 B 村与 B 村到 A 村的路大多不同」。看到这句话，第一反应是「那下标千万别写反」。于是把转移里的 d[i][j] 写成 d[j][i] 试试：

p1171Trans.cpp⚠ 下标全反 —— 300 轮一次都没错

// ⚠ P1171：把转移里的下标写反了（`d[j][i]` 而不是 `d[i][j]`）——**看着像 bug，实测一次都没错**
//
// 草稿里我把它当成第三个错法写进来了，理由听着很顺：
// 「题面明写 A→B 和 B→A 的路大多不同 ⇒ 下标反了当然会错」。
//
// ★★★ 300 轮实测：**被抓 0 次**，它和正解**逐组相同**。两行就能证明为什么：
//   下标全反 ⇒ 它算的是**把每条边方向反过来**那张图上的 TSP；
//   而一条回路 1 → a → b → … → 1 反着走就是 1 → … → b → a → 1，
//   **用到的边正好是反向图里的对应边，总长一个不差**
//   ⇒ 两张图的最优回路**一一对应、长度相等** ⇒ 答案恒等。
//
// ⚠ 所以题面那句「大多不同」对**这个**写法是**噪声**；
//    但它对下一份（p1171Min.cpp）是**命门** —— **同一句约束，对不同的写法分量不同。**

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n) || n <= 0) return 0;
    vector<vector<int>> d(n, vector<int>(n));
    for (auto& row : d) for (auto& x : row) cin >> x;
    if (n == 1) { cout << 0 << '\n'; return 0; }

    const int INF = INT_MAX / 4;
    int full = (1 << n) - 1;
    vector<vector<int>> f(1 << n, vector<int>(n, INF));
    f[1][0] = 0;
    for (int S = 0; S <= full; S++)
        for (int i = 0; i < n; i++) {
            if (f[S][i] >= INF || !(S >> i & 1)) continue;
            for (int j = 0; j < n; j++) {
                if (S >> j & 1) continue;
                int& t = f[S | 1 << j][j];
                t = min(t, f[S][i] + d[j][i]);           // ← 下标反了
            }
        }
    int ans = INF;
    for (int i = 1; i < n; i++)
        if (f[full][i] < INF) ans = min(ans, f[full][i] + d[0][i]);   // ← 这儿也反了
    cout << ans << '\n';
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

★★★ 300 轮被抓 0 次，而且两行就能证明为什么

下标全反 ⇒ 它算的是把每条边方向反过来那张图上的 TSP。而一条回路 1 → a → b → … → 1 反着走就是 1 → … → b → a → 1：用到的边正好是反向图里的对应边，总长一个不差 ⇒ 两张图的最优回路一一对应、长度相等 ⇒ 答案恒等。

⚠⚠ 而「一次都没错」这句话是配了自检才敢写的（P2240、P1094 那条通用规矩）—— 自检就在下面这张表的最后一行：只反一半（转移用转置、收尾用原图）当场被抓 299 / 300。

300 轮	有向图（照题面）	对称图（违反题面那句）
下标全反（转置）	★ 0	★ 0
对称化成 `min`（下一步）	299	★ 0
最近邻贪心	285	275
⚠ 自检：只反一半	★ 299	——

4★★ 第三个错法：把矩阵当成对称的 —— 同一句题面，对两个写法分量不同

p1171Min.cpp✗ 两个方向取更便宜的那个

// ✗ P1171：把有向图「对称化」了 —— 两个方向取更便宜的那个
//
// 这个错法比「下标写反」真实得多：人看到一个距离矩阵，很容易默认它是对称的，
// 于是顺手写成 `min(d[i][j], d[j][i])`（甚至只是懒得想方向）。
//
// ★ 它算了什么：每条边都变便宜了（或不变）⇒ 它解的是一个**放宽了的问题**
//   ⇒ 它的答案**恒 ≤ 正解**。
// ⇒ ★★ 和 p1171Trans.cpp 正好凑成一对：题面那句「A→B 和 B→A 大多不同」
//   对**转置**那个写法是**噪声**（答案恒等），对**这个**写法是**命门**。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n) || n <= 0) return 0;
    vector<vector<int>> d(n, vector<int>(n));
    for (auto& row : d) for (auto& x : row) cin >> x;
    if (n == 1) { cout << 0 << '\n'; return 0; }

    auto w = [&](int a, int b) { return min(d[a][b], d[b][a]); };   // ← 就是这一句

    const int INF = INT_MAX / 4;
    int full = (1 << n) - 1;
    vector<vector<int>> f(1 << n, vector<int>(n, INF));
    f[1][0] = 0;
    for (int S = 0; S <= full; S++)
        for (int i = 0; i < n; i++) {
            if (f[S][i] >= INF || !(S >> i & 1)) continue;
            for (int j = 0; j < n; j++) {
                if (S >> j & 1) continue;
                int& t = f[S | 1 << j][j];
                t = min(t, f[S][i] + w(i, j));
            }
        }
    int ans = INF;
    for (int i = 1; i < n; i++)
        if (f[full][i] < INF) ans = min(ans, f[full][i] + w(i, 0));
    cout << ans << '\n';
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

每条边都变便宜了（或不变）⇒ 它解的是一个放宽了的问题 ⇒ 恒 ≤ 正解（300 / 300），被抓 299 / 300。

★★★ 于是题面那句「大多不同」到底是什么？——要连着「哪个写法」一起回答

按第 12 章那套三分法（情报 / 命门 / 噪声），判据是同一个动作： 造一档违反它的数据，看有没有任何一版的行为变了。

对转置那个写法：造了对称图，它还是 0 ⇒ 那句话是噪声（它本来就恒对）；
对取 min 那个写法：造了对称图，它从 299 掉到精确的 0 ⇒ 那句话是命门。

⇒ ★★ 「这句约束重不重要」不是题目的属性，是「题目 × 你写的那一版」的属性。 这是本书第一次把同一句约束在同一页上称出两种分量。

5★★★ 第四个错法：忘了加回起点 —— 它是同题单下一道题的正解

p1171NoBack.cpp✗ 少加了最后那段 d[i][0]

// ✗ P1171：忘了加回起点那一段
//
// ★ 它解的是**开放式 TSP**（走遍所有村庄就收工，不用回商店）——
//    那是一个**放宽了的问题**（少了一条必须走的边）⇒ 它的答案**恒 ≤ 正解**。
// ⚠ 这正是[第 28 章正文](/ch/28-bitmask-dp/)里 wrongEnd.cpp 演示的那个错法，
//    而题单里 [P1433 吃奶酪](/sol/p1433/) 要的**恰好就是这个开放式版本** ——
//    ⇒ **同一段代码，在这道题上是 bug，在那道题上是正解。**

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n) || n <= 0) return 0;
    vector<vector<int>> d(n, vector<int>(n));
    for (auto& row : d) for (auto& x : row) cin >> x;
    if (n == 1) { cout << 0 << '\n'; return 0; }

    const int INF = INT_MAX / 4;
    int full = (1 << n) - 1;
    vector<vector<int>> f(1 << n, vector<int>(n, INF));
    f[1][0] = 0;
    for (int S = 0; S <= full; S++)
        for (int i = 0; i < n; i++) {
            if (f[S][i] >= INF || !(S >> i & 1)) continue;
            for (int j = 0; j < n; j++) {
                if (S >> j & 1) continue;
                int& t = f[S | 1 << j][j];
                t = min(t, f[S][i] + d[i][j]);
            }
        }
    int ans = INF;
    for (int i = 1; i < n; i++) ans = min(ans, f[full][i]);   // ← 少加了 d[i][0]
    cout << ans << '\n';
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

★★★ 说清楚它算了什么：它解的是「开放式 TSP」

少了一条必须走的边 ⇒ 又一个放宽了的问题 ⇒ 恒 ≤ 正解（300 / 300），被抓 300 / 300 （⚠ 这是本页唯一被官方样例挡住的错法）。

⚠⚠ 而真正值得记住的是：同题单的下一道题 P1433 吃奶酪要的恰恰就是这个开放式版本（老鼠吃完就收工，不用回原点）。

⇒ ★★★ 同一段代码，在这道题上是 bug，在隔壁那道题上是正解。 这和第 27 章那条「编号基在同一张题单里会翻面」是同一类现象的升级版： 别把「上一道题怎么写」当成这一道题的默认值 —— 两道题挨着放，恰恰是因为它们不一样。

6★ 参照物、规模：两道该动手算的算术题

参照物是 (n−1)! 全排列枚举访问顺序 —— 它和状压 DP 的对照本身就说明了「压的是什么」： 暴力记的是顺序（(n−1)! 条），状压记的是「集合 + 停在哪」（2ⁿ × n 个）。


300 轮：正解 vs 全排列暴力	★ 不一致 0 轮
顶格 `n = 20` 的状态数	`2²⁰ × 20 = 20 971 520`
⇒ `int` 表 / `long long` 表	80 MB / 160 MB（题面给 512 MB）
转移次数	约 `4.2 × 10⁸`
而暴力那边 `19!`	`1.2 × 10¹⁷` ⇒ ★ 差 2.9 亿倍
答案上界	`19 × 999 = 18 981` ⇒ `int` 绰绰有余

⚠ 那个 160 MB 值得多看一眼

正文那份模板用的是 long long（保守）。这道题的答案上界只有 18 981， int 就够 —— 而这一步把内存从 160 MB 砍到 80 MB。题面给 512 MB 所以两种都活，但换一道给 128 MB 的题，这就是 MLE 和 AC 的分界。 ⇒ 又一次第 24 章 P1853 那条：「答案对但跑不完 / 装不下」只能靠算。

p1171Brute.cpp参照物：(n−1)! 全排列（300 轮不一致 0 轮）

7度量程序和生成器

p1171Count.cpp度量程序（本页所有数字都出自它）

p1171Gen.cpp数据生成器

8一页纸


★★ 关键的一步	`f[S][i]`（集合 + 停在哪）—— 推导见正文，本章原题，直接交
★ 第一版	最近邻贪心恒 ≥ 正解，被抓 285/300，错时平均多走 56.40%、最多 182.38%
⚠⚠ 第二个不是 bug	下标全反（转置）恒等于正解（把回路反着走，长度不变）；自检：只反一半 299/300
★★ 第三个错法	对称化成 `min` ⇒ 放宽 ⇒ 恒 ≤ 正解，被抓 299/300
★★★ 同一句题面两种分量	「A→B 与 B→A 大多不同」：对转置是噪声（0 → 0），对取 min 是命门（299 → 0）
★★★ 第四个错法	忘了回起点 ⇒ 它解的是开放式 TSP ⇒ 正是同题单 P1433 的正解
参照物	`(n−1)!` 全排列；300 轮不一致 0 轮
规模	顶格 `2²⁰ × 20` 个状态：`int` 表 80 MB、`long long` 160 MB；答案上界 18 981

洛谷 P1171 售货员的难题

0题目原文（本地存了一份）

输入

输出

1★ 第一版：每次去最近的那个村（最近邻贪心）

2★★ 正解：状压 DP —— 而这道题就是本章的模板题

3⚠⚠ 第二个「错法」根本不是错法 —— 而它同时称出了题面那句话的分量

4★★ 第三个错法：把矩阵当成对称的 —— 同一句题面，对两个写法分量不同

5★★★ 第四个错法：忘了加回起点 —— 它是同题单下一道题的正解

6★ 参照物、规模：两道该动手算的算术题

7度量程序和生成器

8一页纸