?從 0 點(diǎn)出發(fā)，每個(gè)點(diǎn)可以走多次。最后再回到 0 點(diǎn)，問(wèn)最小的距離是多少。

因?yàn)槭菑?0 點(diǎn)出發(fā)，所以每次更新的時(shí)候，我們要保證 0 這個(gè)位置一定要是 1 。

?for 循環(huán)的時(shí)候? i = i | 1;

然后從當(dāng)前節(jié)點(diǎn)，走到下一個(gè)節(jié)點(diǎn)。更新就行了。

?

#include <bits/stdc++.h> using namespace std; #define mem(x,v) memset(x,v,sizeof(x)) const int INF = 0x3f3f3f3f; int dp[1<<15][20]; int s[20][20]; int n; int main(){while(scanf("%d",&n) == 1 && n){n++;for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)scanf("%d",&s[i][j]);for (int k = 0; k < n; k++)for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)s[i][j] = min(s[i][j],s[i][k] + s[k][j]); //Floyd 求最短路。mem(dp,INF); dp[1][0] = 0;for (int i = 0; i < (1 << n); i++){i |= 1; //每次要從 0 出發(fā)，所以 0 的位置必須要是 1；for (int j = 0; j < n; j++)if (i & (1 << j)) //當(dāng)前點(diǎn)必須是走過(guò)的。for (int k = 0; k < n; k++)dp[i | (1 << k)][k] = min(dp[i | (1 << k)][k], dp[i][j] + s[j][k]);}printf("%d\n",dp[(1 << n)-1][0]);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的Hie with the Pie (状压 DP)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。