題目大意：
給一個矩陣 n*m (n m<=200),方格裡如果是0~9表示通過它時要花費的代價，-1表示不能通過它。
矩陣中有k(k<=13)個珠寶，問從任意外邊框出發取走所有珠寶並求走出矩陣的最小的代價。
解題思路：
先dij預處理每一個珠寶到其他其他珠寶的最小花費，不包括自己的花費。然後就是裸的TSP問題了，狀態壓縮dp即可。
dp[i][j]表示最後到達第i個珠寶，且訪問珠寶的狀態為j時，最小的花費。
dd[i][j]表示珠寶i到珠寶j之間的花費，注意此時包括j的花費不包括i的花費。
對於已求出的每一種珠寶狀態更新後面未求出珠寶的狀態。
代碼：
<SPAN style="FONT-SIZE: 14px">#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#define eps 1e-6
#define INF 0x1f1f1f1f
#define PI acos(-1.0)
#define ll __int64
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
//#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
*/
struct Node
{
int id,dis;
//Node(){}
Node(int x,int y)
{
id=x,dis=y;
}
friend bool operator <(const struct Node &a,const struct Node &b)
{
return a.dis>b.dis; //按距離從小到達排序，便於優先隊列找到距離當前寶藏的最小距離
}
};
#define Maxn 220
int dd[20][20];//兩個寶藏之間的距離
int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
int istr[Maxn][Maxn]; //表示珠寶的標號
int sa[Maxn][Maxn],cost[20];//cost[i]表示i寶藏到邊界的最短距離
int n,m,k,hash[20],dp[20][1<<15];
int tmpdis[Maxn*Maxn];//其他寶藏距離當前寶藏的距離
bool vis[Maxn][Maxn];
bool isbor(int x,int y) //是否為邊界
{
if(x==0||x==n-1||y==0||y==m-1)
return true;
return false;
}
bool iscan(int x,int y) //是否在矩陣內部
{
if(x<0||x>=n||y<0||y>=m)
return false;
return true;
}
void dij(int hh,int cur) //迪傑斯特拉算法求
{
memset(tmpdis,INF,sizeof(tmpdis));
memset(vis,false,sizeof(vis));
vis[hh/m][hh%m]=true;
priority_queue<Node>myq;
tmpdis[hh]=0;
myq.push(Node(hh,0));
while(!myq.empty())
{
Node tmp=myq.top(); //把距離當前寶藏距離最小的位置找到
myq.pop();
int tt=tmp.id;
int x=tt/m,y=tt%m;
if(isbor(x,y)) //如果是邊界，更新邊界
cost[cur]=min(cost[cur],tmp.dis);
if(istr[x][y]!=-1) //如果是其他珠寶，更新兩珠寶之間的距離
dd[cur][istr[x][y]]=tmp.dis;
for(int i=0;i<4;i++) //能走
{
int xx=x+dir[i][0],yy=y+dir[i][1];
if(!iscan(xx,yy)||vis[xx][yy])
continue;
if(sa[xx][yy]==-1)
continue;
vis[xx][yy]=true;
int temp=xx*m+yy;
tmpdis[temp]=min(tmpdis[temp],tmp.dis+sa[xx][yy]);
myq.push(Node(temp,tmpdis[temp]));
}
}
}
int main()
{
int t,a,b;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
scanf("%d",&sa[i][j]);
scanf("%d",&k);
memset(istr,-1,sizeof(istr));
for(int i=0;i<k;i++)
{
scanf("%d%d",&a,&b);
istr[a][b]=i;
hash[i]=a*m+b; //將坐標從二維轉化成一維便於處理
}
memset(dd,INF,sizeof(dd));
for(int i=0;i<k;i++) //求出每一個寶藏到其他寶藏的距離
{
cost[i]=INF;
dd[i][i]=0; //寶藏從自己到自己距離為0
dij(hash[i],i); //找到從i到所有的寶藏的最短距離
//printf("i:%d cost:%d\n",i,cost[i]);
}
memset(dp,INF,sizeof(dp));
for(int i=0;i<k;i++)
{ //dp[i][1<<i]是包括i本身花費的，+進來花費cost[i]
dp[i][1<<i]=cost[i]+sa[hash[i]/m][hash[i]%m];
// printf("i:%d dp[i][1<<i]:%d\n",i,dp[i][1<<i]);
}
int lim=1<<k;
for(int i=0;i<lim;i++)
{
for(int j=0;j<k;j++)
{
if(!(i&(1<<j))) //如果沒有經過第j個珠寶
continue;
if(dp[j][i]==INF) //此狀態無效
continue;
for(int p=0;p<k;p++)
{
if(i&(1<<p)) //p沒有經過
continue;
if(dd[j][p]==INF)
continue; //最後經過的變成了p 依據j->p 更新後面的狀態
dp[p][i|(1<<p)]=min(dp[p][i|(1<<p)],dp[j][i]+dd[j][p]);
}//dp[j][i]是已經求得的狀態了
}
}
int ans=INF;
for(int i=0;i<k;i++)
{
// printf("%d %d\n",i,dp[i][lim-1]);
ans=min(ans,dp[i][lim-1]+cost[i]); //從最短路走出去
}
printf("%d\n",ans);
}
return 0;
}
</SPAN>
