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

const int N = 16;
int f[1 << N][N][4], a[N][N];

int main() {
    int n;
    scanf("%d", &n);
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &a[i][j]);
        }
    }
    
    memset(f, 0x3f, sizeof(f));
    
    // 初始化：从每个点开始
    for (int i = 0; i < n; i++) {
        f[1 << i][i][0] = 0;
    }
    
    // 状态转移
    for (int i = 0; i < (1 << n); i++) {
        for (int j = 0; j < n; j++) {
            if ((i >> j) & 1) {
                for (int k = 0; k < n; k++) {
                    int prev_mask = i - (1 << j);
                    
                    // k必须在之前的mask中
                    if ((prev_mask >> k) & 1) {
                        // type 0: 未使用任何加速
                        f[i][j][0] = min(f[i][j][0], f[prev_mask][k][0] + a[k][j]);
                        
                        // type 1: 已使用重力加速
                        f[i][j][1] = min(f[i][j][1], f[prev_mask][k][0]);           // 使用重力加速
                        f[i][j][1] = min(f[i][j][1], f[prev_mask][k][1] + a[k][j]);  // 不使用
                        
                        // type 2: 已使用反重力加速
                        f[i][j][2] = min(f[i][j][2], f[prev_mask][k][0] + 2 * a[k][j]);  // 使用反重力加速
                        f[i][j][2] = min(f[i][j][2], f[prev_mask][k][2] + a[k][j]);  // 不使用
                        
                        // type 3: 两次都已使用
                        f[i][j][3] = min(f[i][j][3], f[prev_mask][k][1] + 2 * a[k][j]);  // 先用重力，再用反重力
                        f[i][j][3] = min(f[i][j][3], f[prev_mask][k][2]);                 // 先用反重力，再用重力
                        f[i][j][3] = min(f[i][j][3], f[prev_mask][k][3] + a[k][j]);  // 两次都用完了
                    }
                }
            }
        }
    }
    
    int res = 1e9;
    for (int i = 0; i < n; i++) {
        res = min(res, f[(1 << n) - 1][i][3]);
    }
    
    printf("%d\n", res);
    return 0;
}

星际空间站跳跃问题题解

一、问题分析

1.1 问题本质解读

这道题表面上是"选择n-1条边连通所有空间站"，但实际上需要恰好进行n-1次跳跃把所有空间站跳完，这是一个非常关键的区别。

如果是"连通所有节点"，那是最小生成树问题
如果是"恰好n-1次跳跃访问所有节点"，这是哈密顿路径问题（Hamiltonian Path）

哈密顿路径要求每个节点恰好访问一次，而n个节点恰好需要n-1条边。这正符合题目要求。

1.2 特殊约束分析

题目要求必须使用两次特殊操作：

重力加速：某次跳跃代价变为0
反重力加速：某次跳跃代价翻倍（乘2）

目标：最小化总代价

二、算法设计

2.1 状态压缩动态规划

由于n ≤ 16，我们可以用状态压缩DP来解决。定义三维状态：

dp[mask][u][state] = 最小代价

其中：

mask：二进制数，表示已访问的空间站集合（例如 101 表示访问了第0和第2个空间站）
u：当前所在的空间站编号（0到n-1）
state：特殊操作的使用状态0：未使用任何加速1：已使用重力加速（某次代价归零）2：已使用反重力加速（某次代价翻倍）3：两次都已使用

2.2 状态转移方程

考虑从状态 (mask, u, state) 转移到 (mask | (1<<v), v, new_state)，即从空间站u跳到空间站v。

情况1：当前state = 0（未使用任何加速）

// 不使用加速，正常跳跃
dp[new_mask][v][0] = min(dp[new_mask][v][0], dp[mask][u][0] + cost[u][v])

// 使用重力加速（这次跳跃代价为0）
dp[new_mask][v][1] = min(dp[new_mask][v][1], dp[mask][u][0])

// 使用反重力加速（这次跳跃代价翻倍）
dp[new_mask][v][2] = min(dp[new_mask][v][2], dp[mask][u][0] + 2 * cost[u][v])

情况2：当前state = 1（已使用重力加速）

// 使用反重力加速（这次跳跃代价翻倍）
dp[new_mask][v][3] = min(dp[new_mask][v][3], dp[mask][u][1] + 2 * cost[u][v])

// 不使用加速（两次都还没用完，但这里必须用完）
// 这个情况需要继续使用反重力加速才能到达state 3

情况3：当前state = 2（已使用反重力加速）

// 使用重力加速（这次跳跃代价为0）
dp[new_mask][v][3] = min(dp[new_mask][v][3], dp[mask][u][2])

情况4：当前state = 3（两次都已使用）

// 正常跳跃
dp[new_mask][v][3] = min(dp[new_mask][v][3], dp[mask][u][3] + cost[u][v])

2.3 初始化

从每个空间站开始都可以作为起点：

for (int i = 0; i < n; i++) {
    dp[1 << i][i][0] = 0;  // 只访问了第i个空间站，且未使用任何加速
}

2.4 答案

ans = min(dp[(1<<n)-1][i][3]) for all i

即在所有空间站都被访问（mask = (1<<n)-1），且两次特殊操作都已使用（state = 3）的情况下，取最小值。

三、代码实现

完整代码

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

const int N = 16;
int f[1 << N][N][4], a[N][N];

int main() {
    int n;
    scanf("%d", &n);
    
    // 读取代价矩阵
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &a[i][j]);
        }
    }
    
    // 初始化所有状态为无穷大
    memset(f, 0x3f, sizeof(f));
    
    // 从每个点开始初始化
    for (int i = 0; i < n; i++) {
        f[1 << i][i][0] = 0;
    }
    
    // 状态转移
    for (int i = 0; i < (1 << n); i++) {
        for (int j = 0; j < n; j++) {
            if ((i >> j) & 1) {  // 如果第j个空间站在当前mask中
                for (int k = 0; k < n; k++) {
                    int prev_mask = i - (1 << j);
                    
                    if ((prev_mask >> k) & 1) {  // k在之前的mask中
                        // state 0: 未使用任何加速
                        f[i][j][0] = min(f[i][j][0], f[prev_mask][k][0] + a[k][j]);
                        
                        // state 1: 已使用重力加速
                        f[i][j][1] = min(f[i][j][1], f[prev_mask][k][0]);              // 使用重力加速（代价0）
                        f[i][j][1] = min(f[i][j][1], f[prev_mask][k][1] + a[k][j]);   // 不使用
                        
                        // state 2: 已使用反重力加速
                        f[i][j][2] = min(f[i][j][2], f[prev_mask][k][0] + 2 * a[k][j]);  // 使用反重力加速（代价翻倍）
                        f[i][j][2] = min(f[i][j][2], f[prev_mask][k][2] + a[k][j]);   // 不使用
                        
                        // state 3: 两次都已使用
                        f[i][j][3] = min(f[i][j][3], f[prev_mask][k][1] + 2 * a[k][j]);  // 先用重力，再用反重力
                        f[i][j][3] = min(f[i][j][3], f[prev_mask][k][2]);                 // 先用反重力，再用重力
                        f[i][j][3] = min(f[i][j][3], f[prev_mask][k][3] + a[k][j]);   // 两次都用完了
                    }
                }
            }
        }
    }
    
    // 答案是所有节点都访问且两次操作都使用的最小代价
    int res = 1e9;
    for (int i = 0; i < n; i++) {
        res = min(res, f[(1 << n) - 1][i][3]);
    }
    
    printf("%d\n", res);
    return 0;
}

四、复杂度分析

时间复杂度

状态数量：O(2ⁿ × n × 4) = O(n × 2ⁿ)
每个状态的转移：O(n)
总时间复杂度：O(n² × 2ⁿ)

当 n = 16 时，约为 16² × 2¹⁶ = 256 × 65536 ≈ 1677万次操作，完全可以接受。

空间复杂度

DP数组大小：(1 << 16) × 16 × 4 = 65536 × 16 × 4 ≈ 420万个int
空间复杂度：O(n × 2ⁿ × 4) = O(n × 2ⁿ)

五、示例分析

示例1

输入：

最优解：

从空间站0出发
跳到空间站2：使用重力加速，代价 = 0（原代价1归零）
跳到空间站1：使用反重力加速，代价 = 1 × 2 = 2（原代价1翻倍）
总代价：0 + 2 = 2

示例2