状压 DP 入门：旅行商问题

// 「一个集合就是一个整数」—— 这一章的地基，以及那条填表顺序的**证明**
//
// 第 3 章用二进制枚举过子集，那时候它只是个「枚举手段」。
// 这一章它要变成**状态**，所以值得把对应关系摊开看一遍。
//
// 这份代码做三件事：
//   ① 把 n 个元素的全部 2ⁿ 个集合按整数从小到大列出来（编号 / 二进制 / 里面有谁）；
//   ② 把常用的几个位运算写成一张对照表；
//   ③ ★ **暴力验证那条填表顺序的理由**：
//      对每一个集合 S 和每一个 j ∉ S，检查 `S < (S | 1<<j)` 是不是永远成立。
//      成立，所以「S 从 0 数到 2ⁿ-1」这个自然顺序，天然满足「依赖先算好」。
//
// ★ 第 ③ 件事才是重点。第 21、23、24、25、26、27 章每一次都要专门想一想填表顺序，
//   这一章的顺序简单得可疑 —— 简单是有理由的，而理由可以**跑出来给你看**。
//
// 用法：./bits [元素个数=4]

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

int main(int argc, char** argv) {
    // ⚠ cout 和 printf 混用（表格用 printf 好对齐），所以不关 ios::sync_with_stdio
    int n = (argc > 1) ? atoi(argv[1]) : 4;
    if (n < 1) n = 1;
    if (n > 5) n = 5;                                    // 再多就刷屏了

    cout << "① " << n << " 个元素，一共 " << (1 << n) << " 个集合：\n\n";
    cout << "  整数   二进制   集合里有谁\n";
    cout << "  ----   ------   --------------------\n";
    for (int S = 0; S < (1 << n); S++) {
        string bin;
        for (int i = n - 1; i >= 0; i--) bin += (S >> i & 1) ? '1' : '0';
        string who;
        for (int i = 0; i < n; i++)
            if (S >> i & 1) who += (who.empty() ? "" : ", ") + to_string(i);
        if (who.empty()) who = "空集";
        printf("  %4d   %6s   {%s}\n", S, bin.c_str(), who.c_str());
    }

    cout << "\n② 常用的几个位运算（拿元素 2 和集合 S 举例）：\n\n";
    cout << "  判断 2 在不在 S 里      S >> 2 & 1\n";
    cout << "  把 2 加进 S             S | (1 << 2)\n";
    cout << "  把 2 从 S 去掉          S & ~(1 << 2)\n";
    cout << "  S 里一共有几个元素      __builtin_popcount(S)\n";
    cout << "  全集                    (1 << n) - 1\n";
    cout << "  枚举 S 的所有子集       for (int T = S; ; T = (T - 1) & S) { … if (!T) break; }\n";

    cout << "\n③ ★ 验证那条填表顺序的理由：加一个元素，整数一定变大\n\n";
    long long checked = 0;
    bool ok = true;
    int worst = -1;
    for (int S = 0; S < (1 << n); S++)
        for (int j = 0; j < n; j++) {
            if (S >> j & 1) continue;                    // j 已经在里面了，不算「加进去」
            int T = S | (1 << j);
            checked++;
            if (!(S < T)) { ok = false; if (worst < 0) worst = S; }
        }
    printf("  检查了 %lld 对「S 和 S 加上一个新元素」，", checked);
    if (ok) cout << "全部都满足 S < S|(1<<j)。\n";
    else cout << "居然有反例（S = " << worst << "）—— 那这一章就白写了。\n";

    cout << "\n  所以：任何一个集合的编号，都严格小于「它再加一个元素」之后的编号。\n";
    cout << "  于是 for (S = 0; S <= full; S++) 这个最朴素的顺序，\n";
    cout << "  自动保证了「转移要用到的那个 S，早就算好了」——\n";
    cout << "  「依赖谁，就先填谁」第六次登场，而这一次它不用你动脑子。\n";
    return 0;
}

// 旅行商问题（TSP）—— 暴力：next_permutation 枚举「访问顺序」的全排列
//
// ★ 它是**完全不同的思路**（第 20 章那条规矩）：
//   这份代码里**没有集合、没有位运算、没有 f 表** ——
//   它就是把「先去哪、再去哪」的所有排法列一遍，各自加一加，取最小。
//   正解那边是「按集合从小到大填表」，两边连状态的概念都没有，对上了才有说服力。
//
// 复杂度 (n-1)!：起点固定是 0 号，剩下 n-1 个城市全排列。
//   n = 10 是 362 880 种走法，n = 12 是 3990 万种 —— 正文第 6 步会实测。
//
// 题意：n 个城市，给出**有向**距离矩阵 d[i][j]（从 i 走到 j 的距离，可能 ≠ d[j][i]）。
//       从 0 号城市出发，**每个城市恰好经过一次**，最后回到 0 号，求最短总路程。
// 输入：第一行 n
//       接下来 n 行、每行 n 个整数，第 i 行第 j 列是 d[i][j]（对角线是 0）
// 输出：最短总路程
//
// ⚠ 距离矩阵**不一定对称**，这一点是特意的 —— 正文第 12 步会看到，
//   一个只造对称矩阵的生成器，会让「方向写反」那个 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<long long>> d(n, vector<long long>(n));
    for (auto& row : d) for (auto& x : row) cin >> x;
    if (n == 1) { cout << 0 << "\n"; return 0; }

    vector<int> order(n - 1);
    for (int i = 0; i < n - 1; i++) order[i] = i + 1;    // 要全排列的是 1 ~ n-1

    long long best = LLONG_MAX;
    do {
        long long sum = 0;
        int cur = 0;
        for (int v : order) { sum += d[cur][v]; cur = v; }
        sum += d[cur][0];                                // ★ 别忘了回起点这一段
        best = min(best, sum);
    } while (next_permutation(order.begin(), order.end()));

    cout << best << "\n";
    return 0;
}

// 旅行商问题（TSP）—— 正解：状态压缩 DP
//
// ★ 关键一步（一）：**一个集合就是一个整数。**
//   第 i 位是 1，就表示第 i 个城市已经去过了。n 个城市一共 `1 << n` 个集合。
//   这件事你在**第 3 章**（二进制枚举子集）就见过了，只不过那时候它是「枚举手段」，
//   这一章它要变成「**状态**」。
//
//     判断 i 在不在集合里     S >> i & 1
//     把 i 加进集合           S | (1 << i)
//     全集（n 个元素）        (1 << n) - 1
//
// 状态：f[S][i] = 已经走过的城市集合恰好是 S（且 i ∈ S），此刻**人停在 i**，
//                 从 0 号出发走到这里的最短路程。
//
//   ⚠ 为什么状态里非要带上「停在哪」：因为下一步要走多远，取决于当前在哪 ——
//     光知道「去过哪些城市」是接不下去的。
//     这和第 22 章「以 i 结尾」、第 27 章「这个点选不选」是**同一条道理**：
//     **状态要带上后面还会用到的那一点信息。**
//
// 转移（往前推）：从 (S, i) 走到还没去过的 j
//
//     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 从 0 数到 (1<<n)-1，自然顺序。**
//   理由一行就能说清：`S | (1<<j)` 里 j ∉ S，所以它比 S **多一个 1**，
//   作为整数**一定严格大于 S**。于是「小的先算」自动满足了依赖。
//   「依赖谁，就先填谁」（第 21 章）第六次登场 ——
//   这一次那个顺序简单得可疑，但理由和前五次一模一样。
//   （wrongOrder.cpp 把 S 倒过来枚举，看看会怎样。）
//
// 复杂度 O(2ⁿ × n²)，空间 O(2ⁿ × n)。n = 20 时 2²⁰ × 400 ≈ 4 亿，还能跑；
// 而暴力那边 19! 是个 17 位数。**状压 DP 的适用范围就写在指数里：n 通常 ≤ 20。**
// 输入输出同 brute.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<long long>> d(n, vector<long long>(n));
    for (auto& row : d) for (auto& x : row) cin >> x;
    if (n == 1) { cout << 0 << "\n"; return 0; }

    const long long INF = LLONG_MAX / 4;                 // ⚠ 除以 4，留出加法的余地
    int full = (1 << n) - 1;
    vector<vector<long long>> f(1 << n, vector<long long>(n, INF));
    f[1][0] = 0;                                         // 出发：只去过 0 号，人在 0 号

    for (int S = 0; S <= full; S++)                      // ★ 自然顺序，因为子集的编号一定更小
        for (int i = 0; i < n; i++) {
            if (f[S][i] >= INF) continue;                // 这个局面根本到不了
            if (!(S >> i & 1)) continue;                 // i 必须在 S 里，否则「停在 i」无意义
            for (int j = 0; j < n; j++) {
                if (S >> j & 1) continue;                // j 已经去过了
                int T = S | (1 << j);                    // T > S，所以它还没被处理到
                f[T][j] = min(f[T][j], f[S][i] + d[i][j]);
            }
        }

    long long best = LLONG_MAX;
    for (int i = 1; i < n; i++)
        if (f[full][i] < INF) best = min(best, f[full][i] + d[i][0]);   // ★ 回起点

    cout << best << "\n";
    return 0;
}

// 把整张 f[S][i] 表按集合编号从小到大打出来 —— 动画就是照着这个次序填的
//
// 为什么要有它：动画是用 TypeScript 把这个算法重写一遍画出来的。
// 只比最后那个答案是不够的 —— 答案蒙对、中间过程画错，学生一样看不出来。
// 所以这里把每一个状态的值都打出来，check:viz 拿它和动画**逐格**对照。
// （第 23、26、27 章的 trace.cpp 是同样的用意。）
//
// ★ 这张表本身就是这一章的 ★ 的样子：
//   从上往下看，集合编号是 0、1、2、3…… 一路递增；
//   而每一行用到的都只是**上面**某一行的值 —— 因为「加一个元素，整数一定变大」。
//   `-` 表示这个局面根本到不了（比如「集合里没有 0 号，人却停在 0 号」）。
//
// 用法：./trace            （用正文那组默认的 4 个城市）
//       ./trace < 数据文件（格式同 brute.cpp）

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

int main() {
    // ⚠ cout 和 printf 混用（表格用 printf 好对齐），所以不关 ios::sync_with_stdio
    int n;
    vector<vector<long long>> d;
    if (cin >> n && n > 0) {
        d.assign(n, vector<long long>(n));
        for (auto& row : d) for (auto& x : row) cin >> x;
    } else {
        n = 4;                                           // 正文那组默认数据
        d = {{0, 1, 4, 5}, {2, 0, 9, 1}, {7, 9, 0, 7}, {6, 9, 2, 0}};
    }

    const long long INF = LLONG_MAX / 4;
    int full = (1 << n) - 1;
    vector<vector<long long>> f(1 << n, vector<long long>(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) continue;
            if (!(S >> i & 1)) continue;
            for (int j = 0; j < n; j++) {
                if (S >> j & 1) continue;
                int T = S | (1 << j);
                f[T][j] = min(f[T][j], f[S][i] + d[i][j]);
            }
        }

    cout << "城市数 " << n << "，起点 0 号。f[S][i] = 走过的城市集合是 S、人停在 i 的最短路程。\n\n";
    // ⚠「集合」是 2 个汉字 = 4 格宽，而数据那一列宽 4n+2；不能靠 %-*s（它数字节）
    cout << "   S   二进制   集合" << string(4 * n + 2 - 4, ' ');
    for (int i = 0; i < n; i++) printf("   f[S][%d]", i);
    cout << "\n";
    cout << "  --   ------   " << string(4 * n + 2, '-');
    for (int i = 0; i < n; i++) cout << "   -------";
    cout << "\n";

    for (int S = 0; S <= full; S++) {
        string bin;
        for (int i = n - 1; i >= 0; i--) bin += (S >> i & 1) ? '1' : '0';
        string who;
        for (int i = 0; i < n; i++) if (S >> i & 1) who += to_string(i);
        if (who.empty()) who = "";
        printf("  %2d   %6s   %-*s", S, bin.c_str(), 4 * n + 2, ("{" + who + "}").c_str());
        for (int i = 0; i < n; i++) {
            if (f[S][i] >= INF) printf("   %7s", "-");
            else printf("   %7lld", f[S][i]);
        }
        cout << "\n";
    }

    cout << "\n走遍所有城市之后，还要回起点 —— 每个结尾各算一次：\n";
    long long best = LLONG_MAX;
    int bi = -1;
    for (int i = 1; i < n; i++) {
        if (f[full][i] >= INF) continue;
        printf("  停在 %d 号：f[%d][%d] = %lld，加上回程 d[%d][0] = %lld，一共 %lld\n",
               i, full, i, f[full][i], i, d[i][0], f[full][i] + d[i][0]);
        if (f[full][i] + d[i][0] < best) { best = f[full][i] + d[i][0]; bi = i; }
    }
    cout << "\n答案 = " << best << "（最后停在 " << bi << " 号那一条）\n";
    cout << "每一行用到的都只是上面某一行 —— 因为「加一个元素，整数一定变大」。\n";
    return 0;
}

// ✗ 错误版本二：初值设成 0 而不是 ∞
//
// 求最小值的 DP，初值必须是「不可能达到的大数」。设成 0 之后，
// **每一个还没算出来的局面都被当成了「白送的 0 代价」** ——
// 于是 min 会一路取到那些根本到不了的格子上。
//
// ★ 这个 bug 的答案总是**偏小**，而且小得很有规律：
//   f[S][i] 恒等于 0（任何格子都能从「0 代价」出发），
//   所以最后输出的就是 **min over i≠0 of d[i][0]** —— 一个只和「谁到起点最近」有关的数，
//   和整条路线毫无关系。正文第 12 步用 300 组数据把这条钉死了。
//
// ⚠ 这是第 23 章 `exact.cpp` 那一节的回声：
//   **初值不是「随便填个数」，初值是在回答「哪些局面根本不存在」。**
//   求最大值就填 -∞，求最小值就填 +∞，只有真正的起点才填 0。
//
// 输入输出同 brute.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<long long>> d(n, vector<long long>(n));
    for (auto& row : d) for (auto& x : row) cin >> x;
    if (n == 1) { cout << 0 << "\n"; return 0; }

    int full = (1 << n) - 1;
    vector<vector<long long>> f(1 << n, vector<long long>(n, 0));     // ✗ 应该是 INF
    f[1][0] = 0;

    for (int S = 0; S <= full; S++)
        for (int i = 0; i < n; i++) {
            if (!(S >> i & 1)) continue;
            for (int j = 0; j < n; j++) {
                if (S >> j & 1) continue;
                int T = S | (1 << j);
                f[T][j] = min(f[T][j], f[S][i] + d[i][j]);
            }
        }

    long long best = LLONG_MAX;
    for (int i = 1; i < n; i++) best = min(best, f[full][i] + d[i][0]);

    cout << best << "\n";
    return 0;
}

// ✗ 错误版本三：最后忘了加回起点那一段 d[i][0]
//
// 整张表都填对了，只在最后一行栽了：
//
//     正确： best = min(f[full][i] + d[i][0])
//     错误： best = min(f[full][i])
//
// ★ 它不是随机地错，它**精确地解了另一道题**：
//   **开放式旅行商 —— 从 0 号出发走遍所有城市，但不用回来**（也就是最短哈密顿路径）。
//   那是一道真实存在、也很常考的题（比如洛谷 P1433 吃奶酪就是不用回来的）。
//
//   所以这一条又是「写错了就是另一道题」那个系列的一员（这是第九条）。
//   正文第 12 步用 300 组数据钉死了它：
//   **wrongEnd.cpp 的输出恒等于 openTsp.cpp（老老实实写的开放式 TSP），一组不差。**
//
// ⚠ 现实里这个 bug 特别容易犯，因为两道题的题面只差「回到出发点」五个字。
//   **题目对边界的约定要抄进注释**（第 19 章那条规矩）—— 这就是个活例子。
//
// 输入输出同 brute.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<long long>> d(n, vector<long long>(n));
    for (auto& row : d) for (auto& x : row) cin >> x;
    if (n == 1) { cout << 0 << "\n"; return 0; }

    const long long INF = LLONG_MAX / 4;
    int full = (1 << n) - 1;
    vector<vector<long long>> f(1 << n, vector<long long>(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) continue;
            if (!(S >> i & 1)) continue;
            for (int j = 0; j < n; j++) {
                if (S >> j & 1) continue;
                int T = S | (1 << j);
                f[T][j] = min(f[T][j], f[S][i] + d[i][j]);
            }
        }

    long long best = LLONG_MAX;
    for (int i = 1; i < n; i++)
        if (f[full][i] < INF) best = min(best, f[full][i]);   // ✗ 少了 + d[i][0]

    cout << best << "\n";
    return 0;
}

// ✗ 错误版本六：最后只看了「停在 n-1 号」的那一个状态，忘了对所有结尾取 min
//
//     正确： best = min over i≠0 of ( f[full][i] + d[i][0] )
//     错误： best =                    f[full][n-1] + d[n-1][0]
//
// 走遍所有城市之后，人可以停在任何一个城市，回程的那一段各不相同 ——
// 必须把 n-1 种可能都试一遍。只看一个，等于凭空规定「最后一个必须是 n-1 号」。
//
// ★ 它的抓获率**跟着城市数变**，这一点很有用：
//   最优路线的终点在 n-1 个城市里大致是随机的，所以这份代码大约有 1/(n-1) 的概率蒙对。
//   n = 4 时四分之一的数据抓不住，n = 9 时只剩八分之一 ——
//   **城市数越少，它越安全。** 正文第 12 步那张表把这条量出来了。
//
//   这和第 26 章「堆数太少，错误贪心就隐身」是同一类现象：
//   **规模小 = 可能性少 = 蒙对的概率大。**
//
// 输入输出同 brute.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<long long>> d(n, vector<long long>(n));
    for (auto& row : d) for (auto& x : row) cin >> x;
    if (n == 1) { cout << 0 << "\n"; return 0; }

    const long long INF = LLONG_MAX / 4;
    int full = (1 << n) - 1;
    vector<vector<long long>> f(1 << n, vector<long long>(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) continue;
            if (!(S >> i & 1)) continue;
            for (int j = 0; j < n; j++) {
                if (S >> j & 1) continue;
                int T = S | (1 << j);
                f[T][j] = min(f[T][j], f[S][i] + d[i][j]);
            }
        }

    // ✗ 只看了一个结尾，没有对所有 i 取 min
    cout << f[full][n - 1] + d[n - 1][0] << "\n";
    return 0;
}

// ✗ 错误版本四：转移里把 d[i][j] 写成了 d[j][i] —— 方向反了
//
// 人是从 i 走到 j，代价当然是 d[i][j]。写成 d[j][i] 就是「按回程的价钱付去程的钱」。
//
// ★ 这个 bug 是这一章的**主角**，但不是因为它难写对，
//   而是因为**绝大多数人造的数据根本抓不住它**：
//
//   随手写一个距离矩阵生成器，最自然的写法是
//   「随机一个上三角，然后镜像下去」—— 于是 d[i][j] == d[j][i]，
//   **方向写反和写对是同一件事**，这份代码一轮都不会错。
//
//   正文第 12 步实测：只造对称矩阵的数据上它是 **0 / 300**，
//   矩阵改成不对称之后立刻变成 **300 / 300**。
//
//   第 27 章刚踩过一次同类的坑（「1 号永远当根」让「没找根」隐身），
//   这一次换了个维度：**对称性**。两次的教训是同一句话 ——
//   **数据的随机性不能只在数值上，结构上的「巧合」同样要打破。**
//
// ⚠ 现实里 TSP 的距离常常真的是对称的（欧氏距离就是），
//   所以这个 bug 在很多题上确实无害。但「无害」和「对」是两回事：
//   题目一旦给的是有向图（单行道、上坡下坡、机票价格），它立刻就错。
//
// 输入输出同 brute.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<long long>> d(n, vector<long long>(n));
    for (auto& row : d) for (auto& x : row) cin >> x;
    if (n == 1) { cout << 0 << "\n"; return 0; }

    const long long INF = LLONG_MAX / 4;
    int full = (1 << n) - 1;
    vector<vector<long long>> f(1 << n, vector<long long>(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) continue;
            if (!(S >> i & 1)) continue;
            for (int j = 0; j < n; j++) {
                if (S >> j & 1) continue;
                int T = S | (1 << j);
                f[T][j] = min(f[T][j], f[S][i] + d[j][i]);   // ✗ 应该是 d[i][j]
            }
        }

    long long best = LLONG_MAX;
    for (int i = 1; i < n; i++)
        if (f[full][i] < INF) best = min(best, f[full][i] + d[i][0]);

    cout << best << "\n";
    return 0;
}

// 输出**走法本身** —— 第 26、27 章那套回溯，在状压 DP 上再用一次
//
// 还是那句话（第 23 章欠的账，第 26 章开始还）：要方案就得把「这一步是从哪来的」记下来。
// 这里记的是 `from[S][i]` = 走到「集合 S、停在 i」这个局面之前，人在哪个城市。
//
//   回溯时把 i 从集合里去掉（`S & ~(1 << i)`），就退回到上一个局面 ——
//   ★ 这一步正好把「集合就是整数」用了个彻底：**删一个元素也只是一次位运算。**
//
// check:viz 对这份输出做的是**硬验证**，不是比字符串：
//   路线必须从 0 出发、每个城市恰好经过一次、最后回到 0，
//   而且逐段距离加起来必须正好等于第一行那个答案。
//
// 用法：./path            （用正文那组默认的 4 个城市）
//       ./path < 数据文件（格式同 brute.cpp）

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

int main() {
    // ⚠ cout 和 printf 混用（表格用 printf 好对齐），所以不能关 ios::sync_with_stdio
    //   —— 关了两边各自缓冲，表格会跑到结语后面去（第 26 章踩过，这次又踩了一遍）
    int n;
    vector<vector<long long>> d;
    if (cin >> n && n > 0) {
        d.assign(n, vector<long long>(n));
        for (auto& row : d) for (auto& x : row) cin >> x;
    } else {
        n = 4;
        d = {{0, 1, 4, 5}, {2, 0, 9, 1}, {7, 9, 0, 7}, {6, 9, 2, 0}};
    }
    if (n == 1) { cout << "最短总路程 = 0\n路线：0 -> 0\n"; return 0; }

    const long long INF = LLONG_MAX / 4;
    int full = (1 << n) - 1;
    vector<vector<long long>> f(1 << n, vector<long long>(n, INF));
    vector<vector<int>> from(1 << n, vector<int>(n, -1));
    f[1][0] = 0;

    for (int S = 0; S <= full; 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 = S | (1 << j);
                if (f[S][i] + d[i][j] < f[T][j]) {
                    f[T][j] = f[S][i] + d[i][j];
                    from[T][j] = i;                      // ← 全部的额外开销就是这一行
                }
            }
        }

    long long best = LLONG_MAX;
    int endCity = -1;
    for (int i = 1; i < n; i++)
        if (f[full][i] < INF && f[full][i] + d[i][0] < best) {
            best = f[full][i] + d[i][0];
            endCity = i;
        }

    // 回溯：从「全集、停在 endCity」一路退回起点
    vector<int> route;
    int S = full, cur = endCity;
    while (cur != -1) {
        route.push_back(cur);
        int prev = from[S][cur];
        S &= ~(1 << cur);                                // ★ 把当前城市从集合里去掉
        cur = prev;
    }
    reverse(route.begin(), route.end());

    cout << "最短总路程 = " << best << "\n\n";
    cout << "路线：";
    for (size_t i = 0; i < route.size(); i++) cout << route[i] << " -> ";
    cout << "0\n\n";

    cout << "  第几段   从 -> 到   这一段   累计\n";
    cout << "  ------   --------   ------   ----\n";
    long long acc = 0;
    for (size_t i = 0; i + 1 < route.size(); i++) {
        acc += d[route[i]][route[i + 1]];
        printf("  %6zu   %3d -> %-2d   %6lld   %4lld\n",
               i + 1, route[i], route[i + 1], d[route[i]][route[i + 1]], acc);
    }
    acc += d[route.back()][0];
    printf("  %6zu   %3d -> %-2d   %6lld   %4lld   <- 回起点这一段最容易忘\n",
           route.size(), route.back(), 0, d[route.back()][0], acc);

    cout << "\n  一共经过 " << route.size() << " 个城市各一次，再回到 0 号，累计 " << acc << "。\n";
    return 0;
}

// 旅行商问题（TSP）—— 正解：状态压缩 DP
//
// ★ 关键一步（一）：**一个集合就是一个整数。**
//   第 i 位是 1，就表示第 i 个城市已经去过了。n 个城市一共 `1 << n` 个集合。
//   这件事你在**第 3 章**（二进制枚举子集）就见过了，只不过那时候它是「枚举手段」，
//   这一章它要变成「**状态**」。
//
//     判断 i 在不在集合里     S >> i & 1
//     把 i 加进集合           S | (1 << i)
//     全集（n 个元素）        (1 << n) - 1
//
// 状态：f[S][i] = 已经走过的城市集合恰好是 S（且 i ∈ S），此刻**人停在 i**，
//                 从 0 号出发走到这里的最短路程。
//
//   ⚠ 为什么状态里非要带上「停在哪」：因为下一步要走多远，取决于当前在哪 ——
//     光知道「去过哪些城市」是接不下去的。
//     这和第 22 章「以 i 结尾」、第 27 章「这个点选不选」是**同一条道理**：
//     **状态要带上后面还会用到的那一点信息。**
//
// 转移（往前推）：从 (S, i) 走到还没去过的 j
//
//     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 从 0 数到 (1<<n)-1，自然顺序。**
//   理由一行就能说清：`S | (1<<j)` 里 j ∉ S，所以它比 S **多一个 1**，
//   作为整数**一定严格大于 S**。于是「小的先算」自动满足了依赖。
//   「依赖谁，就先填谁」（第 21 章）第六次登场 ——
//   这一次那个顺序简单得可疑，但理由和前五次一模一样。
//   （wrongOrder.cpp 把 S 倒过来枚举，看看会怎样。）
//
// 复杂度 O(2ⁿ × n²)，空间 O(2ⁿ × n)。n = 20 时 2²⁰ × 400 ≈ 4 亿，还能跑；
// 而暴力那边 19! 是个 17 位数。**状压 DP 的适用范围就写在指数里：n 通常 ≤ 20。**
// 输入输出同 brute.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<long long>> d(n, vector<long long>(n));
    for (auto& row : d) for (auto& x : row) cin >> x;
    if (n == 1) { cout << 0 << "\n"; return 0; }

    const long long INF = LLONG_MAX / 4;                 // ⚠ 除以 4，留出加法的余地
    int full = (1 << n) - 1;
    vector<vector<long long>> f(1 << n, vector<long long>(n, INF));
    f[1][0] = 0;                                         // 出发：只去过 0 号，人在 0 号

    for (int S = 0; S <= full; S++)                      // ★ 自然顺序，因为子集的编号一定更小
        for (int i = 0; i < n; i++) {
            if (f[S][i] >= INF) continue;                // 这个局面根本到不了
            if (!(S >> i & 1)) continue;                 // i 必须在 S 里，否则「停在 i」无意义
            for (int j = 0; j < n; j++) {
                if (S >> j & 1) continue;                // j 已经去过了
                int T = S | (1 << j);                    // T > S，所以它还没被处理到
                f[T][j] = min(f[T][j], f[S][i] + d[i][j]);
            }
        }

    long long best = LLONG_MAX;
    for (int i = 1; i < n; i++)
        if (f[full][i] < INF) best = min(best, f[full][i] + d[i][0]);   // ★ 回起点

    cout << best << "\n";
    return 0;
}