蓝桥杯刷题-毕业旅行问题

731. 毕业旅行问题 - AcWing题库

/* 起点变为1 ~ n - 1号点，终点变为0号点 */
#include <bits/stdc++.h>
 
using namespace std;
#define x first
#define y second
typedef long long LL;
typedef pair<int , int> PII;
 
const int N = 10 , M = (1 << N);
int dp[M][N] , w[N + 1][N + 1];
int n , b[N];
 
int main()
{
    cin >> n;
    int fal = 1 << n;
    for(int i = 0;i < n ; i ++) b[i] = 1 << i; 
 
    for(int i = 0;i < n;i ++)
    {
        for(int j = 0;j < n; j ++)
            cin >> w[i][j];
    }
 
    memset(dp, 0x3f , sizeof dp);
    for(int i = 1;i < n;i ++) dp[b[i]][i] = w[0][i];
 
    for(int st = 0;st < fal; st ++)
    {
        /* 状态必须要经过起点 */
        if(st & 1 && st != fal - 1) continue;
        for(int i = 0;i < n ; i ++)
        {
            /* 状态必须要经过i号点 */
            if(!(st >> i & 1)) continue;
            for(int j = 0;j < n; j ++)
            /* 状态必须要经过j号点 */
                if((st - b[i]) >> j & 1) 
                    dp[st][i] = min(dp[st - b[i]][j] + w[j][i] , dp[st][i]);
 
        }
    }
    /* 最终状态为全1 */
    cout << dp[fal - 1][0];
 
    return 0;
}