HDU Victor and World (最短路+狀態壓縮)

題目鏈接：傳送門

題意：

n個城市m條路，剛開始在點1，求把每個城市都遍歷一邊最後回到1的花費的最小值。

分析：

我們首先需要預處理出任意兩個國家之間的最短距離，因為數據范圍很小，所以直接用Floyd就行了。之後，我們用f[S][i]表示訪問國家的情況為S，當前最後訪問的一個國家是i所需要的最小總油量，其中，S的二進制表示記錄了訪問國家的情況，S在二進制表示下的第i位（不管是從左往右還是從右往左都可以）如果是1則表示第i個國家被訪問過了，否則表示第i個國家沒有被訪問過，那麼f[S|(1<

轉自Bestcode。

下面說說我的狀態轉移，首先也處理好了每兩個城市之間的最短路。

然後DP[S][J]S轉換成二進制後1代表去過,0代表沒有去過最後留在J的最小花費，然後就枚舉S沒有去過的城市k

DP[S|(1<

代碼如下：

#include 
#include 
#include 
#include 
using namespace std;

const int maxn = 18;

const int inf = 0x3f3f3f3f;

int dp[1<