#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, dis[25][25], ans = LLONG_MAX;
int dp[1048580][25];
signed main() {
memset(dp, 0x3f, sizeof dp);
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> dis[i][j];
}
}
dp[1][0] = 0;
for (int i = 1; i < (1 << n); i++) {
for (int j = 0; j < n; j++) {
if (i & (1 << j)) {
for (int k = 0; k < n; k++) {
if ((i & (1 << k)) == 0) dp[(1 << k) | i][k] = min(dp[(1 << k) | i][k], dp[i][j] + dis[j][k]);
}
}
}
}
for (int i = 0; i < n; i++) ans = min(ans, dp[(1 << n) - 1][i]);
cout << ans;
return 0;
}
你好，我看看，稍等 
你好，你这个最后的ans取得有点问题，他默认是从1商店回到1商店，你的状态转移是对的，但是中间那个循环求不了dp[(1<<n)-1][0]，（因为（1<<n）-1会发现已经有0了），所以你最后求ans的时候应该for(int i=1;i<n;i++)
{
ans=min(ans,dp[(1<<n)-1][i]+dis[i][0]);
}
刚试了一下，过了
谢谢老师
1 个赞