思路：

  • 类似于 算法竞赛进阶指南 中的例题 最短Hamilton路径 ，只是多了一个”跳跃“的属性
  • 对于原例题，我们采取 状压dp 的思路来求得以每一个状态结束时的最优解
    • 有两维：当前选取值（二进制串）、当前所在位置
  • 对于本题，我们考虑分层图的思路（记录一个类似的状态）也就是记录当前跳跃了几次。 
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ull unsigned long long

typedef pair<int, int> pii;
typedef pair<int, char> pic;

const int N = 16;
const int mod = 1e9 + 7;

int n, a[N][N];
int dp[1 << N][N][3];
int main() {
    cin >> n;
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < n; j ++)
            cin >> a[i][j];
    memset(dp, 0x3f, sizeof(dp));
    for(int i = 0; i < n; i ++) dp[1 << i][i][0] = 0;
    for(int i = 1; i < (1 << n); i ++) {
        for(int j = 0; (1 << j) <= i; j ++) {
            if(((1 << j) & i) == 0) continue;
            int x = (1 << j) ^ i;
            for(int k = 0; (1 << k) <= x; k ++) {
                if(((1 << k) & x) == 0) continue;
                dp[i][j][0] = min(dp[i][j][0], dp[x][k][0] + a[k][j]);
                dp[i][j][1] = min(dp[i][j][1], min(dp[x][k][0], dp[x][k][1] + a[k][j]));
                dp[i][j][2] = min(dp[i][j][2], min(dp[x][k][2] + a[k][j], dp[x][k][1] + 2 * a[k][j]));     
            }
        }
    }
    int ans = 0x3fffffff;
    for(int i = 0; i < n; i ++)
        ans = min(ans, dp[(1 << n) - 1][i][2]);
    cout << ans;
    return 0;
}