Hie with the Pie

題目鏈接：POJ 3311

題目大意

給你 n+1 個點，其中 0 號點是特殊點。
然后兩個點之間都有路徑可以走。
然后你要從特殊點出發走過所有點回到特殊點，問你最短路徑。

思路

不難看出是狀壓 DP。
直接設 $f_{i,j}$ 為每個點的走過狀態為 $i$，最后走的點是 $j$。

然后直接枚舉下一個點轉移即可。
然后答案就是枚舉 $i$，是 $f_{2^n?1,i}+a_{i,0}$ 的最小值。
（因為你還要走回來）

然后你直接用給你的 $a$ 做會錯。
因為你不一定要走圖上給你的邊，你走 $1\to 3$ 可能可以 $1\to 2,2\to 3$，這樣可能反而更優。（就比如第一個邊權是 $10$，后面兩個邊權是 $1$）
所以我們先對 $a$ 跑 Floyed 算法求出兩兩點最短路，就可以做了。

代碼

#include<cstdio> #include<cstring> #include<iostream> #define ll long long #define INF 0x3f3f3f3f3f3f3f3f using namespace std;int n, a[11][11]; ll f[1024][11];int main() {scanf("%d", &n);while (n) {for (int i = 0; i <= n; i++)for (int j = 0; j <= n; j++)scanf("%d", &a[i][j]);memset(f, 0x7f, sizeof(f));for (int k = 0; k <= n; k++)//Floyedfor (int i = 0; i <= n; i++)for (int j = 0; j <= n; j++)a[i][j] = min(a[i][j], a[i][k] + a[k][j]);for (int i = 1; i <= n; i++)f[1 << (i - 1)][i] = a[0][i];for (int i = 0; i < (1 << n); i++) {//原來狀態for (int j = 1; j <= n; j++)//最后一個到的點是哪個if ((i >> (j - 1)) & 1) {for (int k = 1; k <= n; k++)//現在要去的點是哪if (!((i >> (k - 1)) & 1)) {f[i | (1 << (k - 1))][k] = min(f[i | (1 << (k - 1))][k], f[i][j] + a[j][k]);}}}ll ans = INF;for (int i = 1; i <= n; i++) ans = min(ans, f[(1 << n) - 1][i] + a[i][0]);//枚舉最后到的點加上回來的時間printf("%lld\n", ans);scanf("%d", &n);}return 0; }

總結

以上是生活随笔為你收集整理的【POJ 3311】Hie with the Pie（状压DP）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。