題目描述

某鄉(xiāng)有n個(gè)村莊( 1 < n <= 16 )，有一個(gè)售貨員，他要到各個(gè)村莊去售貨，各村莊之間的路程s(0 < s < 1000)是已知的，且A村到B村與B村到A村的路大多不同。為了提高效率，他從商店出發(fā)到每個(gè)村莊一次，然后返回商店所在的村，假設(shè)商店所在的村莊為1，他不知道選擇什么樣的路線才能使所走的路程最短。請(qǐng)你幫他選擇一條最短的路。

輸入輸出格式

輸入格式：

第一行一個(gè)數(shù)n表示村莊數(shù)
接下來(lái)是一個(gè)n×n的矩陣，表示各村莊之間的路程。

輸出格式：

最短的路程。

輸入輸出樣例

輸入樣例#1：

3
0 2 1
1 0 2
2 1 0 

輸出樣例#1：

3

思路

這是一道狀壓dp，所以做這道題之前需要先知道一些關(guān)于狀態(tài)壓縮的基本概念。簡(jiǎn)單來(lái)說(shuō)，就是在一般的題目里，一個(gè)數(shù)組即可保存狀態(tài)。但是有這樣的一些題 目，它們具有DP問(wèn)題的特性，但是狀態(tài)中所包含的信息過(guò)多，如果要用數(shù)組來(lái)保存狀態(tài)的話需要四維以上的數(shù)組。于是，我們就需要通過(guò)狀態(tài)壓縮來(lái)保存狀態(tài)，而 使用狀態(tài)壓縮來(lái)保存狀態(tài)的DP就叫做狀態(tài)壓縮DP。例如這道售貨員難題，若有n 個(gè)村莊，想要表示是否經(jīng)過(guò)每個(gè)村莊的狀態(tài)，則需要使用n維數(shù)組，而采取狀態(tài)壓縮，往往利用二進(jìn)制的整數(shù)來(lái)簡(jiǎn)單的表示狀態(tài)，如$0101$，則表示經(jīng)過(guò)了$1$、$3$號(hào)村莊，沒(méi)有經(jīng)過(guò)$2$、$4$號(hào)村莊。

我先介紹一下位運(yùn)算相關(guān)的知識(shí)：

還有幾種在狀壓dp中常見(jiàn)的應(yīng)用如下：
1.判斷一個(gè)數(shù)字x二進(jìn)制下第i位是不是等于1。

方法：if ( ( ( 1 << ( i - 1 ) ) & x ) > 0)

將1左移i-1位，相當(dāng)于制造了一個(gè)只有第i位上是1，其他位上都是0的二進(jìn)制數(shù)。然后與x做與運(yùn)算，如果結(jié)果>0，說(shuō)明x第i位上是1，反之則是0。

2.將一個(gè)數(shù)字x二進(jìn)制下第i位更改成1。

方法：x = x | ( 1<<(i-1) )

證明方法與1類(lèi)似，此處不再重復(fù)證明。

3.把一個(gè)數(shù)字二進(jìn)制下最靠右的第一個(gè)1去掉。

方法：x=x&(x-1)

回過(guò)頭來(lái)看這道題，n<20,使用狀態(tài)壓縮將會(huì)很方便，dp[i][j]表示從起始點(diǎn)到i號(hào)點(diǎn)在j狀態(tài)下花費(fèi)的最短路程，例如n=3,dp[3][3]，即表示從起始點(diǎn)到3號(hào)點(diǎn)，在011，也就是經(jīng)過(guò)了1號(hào)點(diǎn)和2號(hào)點(diǎn)的情況的最短路程。
詳細(xì)的狀態(tài)方程可以見(jiàn)代碼，再填出dp表格后，比較不同的點(diǎn)在經(jīng)過(guò)所有點(diǎn)后到起始點(diǎn)的路程，便可以得到答案

AC代碼：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int map[21][21];
int dp[21][40000]; 
int main()
{int n;cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cin>>map[i][j];}}memset(dp,64,sizeof(dp));dp[1][1]=0;for(int i=0;i<=(1<<n);i++)//枚舉路線{for(int j=1;j<=n;j++)//枚舉村莊 {if(((1<<(j-1))&i)==0)//如果第i號(hào)村莊沒(méi)去過(guò)第j號(hào)村莊就往下 {for(int q=1;q<=n;q++)//枚舉村莊 {if(1<<(q-1)&i)//如果第i號(hào)村莊去了第q號(hào)村莊就往下 {dp[j][1<<j-1|i]=min(dp[j][1<<j-1|i],dp[q][i]+map[q][j]);//dp[j][1<<j-1|i]為：經(jīng)過(guò)i號(hào)村莊去j號(hào)村莊//dp[q][i]+map[q][j]為：經(jīng)過(guò)i號(hào)村莊去q號(hào)村莊，再?gòu)膓號(hào)村莊去j號(hào)村莊//類(lèi)似于Floyd}}}}}int ans=9999999;for(int i=2;i<=n;i++){ans=min(ans,dp[i][(1<<n)-1]+map[i][1]);//判斷從1號(hào)村莊去哪一號(hào)村莊可以更快的跑完}cout<<ans<<endl;return 0;
}