题目链接

未懂：

• a[x,y]+a[y,z]≥a[x,z] 这个条件什么意思？
• 图中两点之间是不是互相可达 ？i的状态一定能保证能从0走到j,走到k吗？

另外这题时限竟然有5s😱，第一次见

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

const int NN = 20, MM = (1 << NN) + 10;
int g[NN][NN], dp[MM][NN];
int n;

int main(){
    cin >> n;
    for (int i = 0; i < n; i ++)
        for (int j = 0; j < n; j ++)
            scanf("%d", &g[i][j]);

    memset(dp, 0x3f, sizeof(dp));   // 求最小值，初始化为最大值
    dp[1][0] = 0;


    // 这里必须要先遍历状态，因为状态转移时要用到比i小的状态i - (1 << j)
    for (int i = 0; i < 1 << n; i ++){ // 每一个状态
        for (int j = 0; j < n; j ++){ // 每一个终点
            if ((i >> j) & 1){ // j 在状态 i 中
                for (int k = 0; k < n; k ++){  // 遍历 j 的前一个点
                    if ((i >> k) & 1){
                        dp[i][j] = min(dp[i][j], dp[i - (1 << j)][k] + g[k][j]);
                    }
                }
            }
        }
    }

    cout << dp[(1 << n) - 1][n - 1];

    return 0;
}