鏈接：https://ac.nowcoder.com/acm/problem/50909
來源：牛客網

時間限制：C/C++ 1秒，其他語言2秒
空間限制：C/C++ 262144K，其他語言524288K
64bit IO Format: %lld
題目描述
給定一張 n(n \leq 20)(n≤20) 個點的帶權無向圖，點從0 \sim n-10～n?1標號，求起點 0 到終點 n-1 的最短Hamilton路徑。 Hamilton路徑的定義是從 0 到 n-1 不重不漏地經過每個點恰好一次。
輸入描述:
第一行一個整數n。
接下來n行每行n個整數，其中第i行第j個整數表示點i到j的距離（一個不超過10^710
7
的正整數，記為a[i,j]）。
對于任意的x,y,z，數據保證 a[x,x]=0，a[x,y]=a[y,x] 并且a[x,y]+a[y,z] \geq a[x,z]a[x,y]+a[y,z]≥a[x,z]。
輸出描述:
一個整數，表示最短Hamilton路徑的長度。
示例1
輸入
復制

4 0 2 1 3 2 0 2 1 1 2 0 1 3 1 1 0

輸出
復制

4

說明
從0到3的Hamilton路徑有兩條，0-1-2-3和0-2-1-3。前者的長度為2+2+1=5，后者的長度為1+2+1=4
/*
狀壓dp:
用 dp[status][k] 表示 經過status這些點，終點是k的最短路。
dp[status][j] = min(dp[status][j],dp[status-(1<<j)][k] + a[k][j])
dp[status-(1<<j)][k] + a[k][j]:
通過k到達j，所以之前j應該為0，
即status減去j狀態（status^(1<<j)也是相同的意思）。

*/

#include <bits/stdc++.h> using namespace std; int a[21][21]; int dp[1<<20][21]; int main() {int n;cin>>n;for(int i = 0; i < n; i++){for(int j = 0; j < n; j++){cin>>a[i][j];}}int inf = 0x3f3f3f3f;memset(dp,inf,sizeof(dp));dp[1][0] = 0; //邊界：狀態1，終點為0，路徑長度為0for(int i = 1; i <(1<<n); i++){for(int j = 0; j < n; j++){if((i>>j)&1)//status中終點為j，此時想再通過其他點到jfor(int k = 0; k < n; k++){dp[i][j] = min(dp[i][j],dp[i^(1<<j)][k] + a[k][j]);}}}cout<<dp[(1<<n)-1][n-1]<<endl;return 0; }

總結

以上是生活随笔為你收集整理的最短Hamilton路径(状压dp)的全部內容，希望文章能夠幫你解決所遇到的問題。

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