记录编号	442002	评测结果	AAAAAAAAAA
题目名称	[WC 2008]游览计划	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.137 s
提交时间	2017-08-26 07:59:09	内存使用	1.88 MiB

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N=20;
int n,m,v[N][N],st[N][N],k,U;
int dp[N][N][1<<10];//dp[i][j][S]表示当前位置是(i,j)，已经联通的集合为S的最小代价
const int fx[4]={1,0,-1,0},fy[4]={0,1,0,-1};
struct sit{
	int x,y,S,cost;
	bool operator > (const sit &a)const{return cost>a.cost;}
};
priority_queue<sit,vector<sit>,greater<sit> > Q;
int vis[N][N];
void dijkstra(int S){//每次只考虑添加一个点
	while (!Q.empty()){
		sit now=Q.top();Q.pop();
		int x=now.x,y=now.y,S=now.S;
		if (vis[x][y]==S) continue;
		vis[x][y]=S;
		for (int i=0;i<4;i++){
			int a=x+fx[i],b=y+fy[i];
			if (a&&a<=n&&b&&b<=m&&dp[a][b][S|st[a][b]]>dp[x][y][S]+v[a][b]){
				dp[a][b][S|st[a][b]]=dp[x][y][S]+v[a][b];
				if ((S|st[a][b])!=S) continue;
				Q.push((sit){a,b,S,dp[a][b][S]});
			}
		}
	}
}
int main()
{
	freopen("wc2008_trip.in","r",stdin);
	freopen("wc2008_trip.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++)
	for (int j=1;j<=m;j++){
		scanf("%d",&v[i][j]);
		if (!v[i][j]) st[i][j]=1<<k,k++;
	}
	U=1<<k;
	for (int i=1;i<=n;i++)
	for (int j=1;j<=m;j++){
		for (int s=0;s<U;s++) dp[i][j][s]=1e9;
		dp[i][j][st[i][j]]=v[i][j];
	}
	for (int S=0;S<U;S++){
		for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
		for (int T=(S-1)&S;T;T=(T-1)&S)
			dp[i][j][S]=min(dp[i][j][S],dp[i][j][T]+dp[i][j][S^T]-v[i][j]);
		for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
			if (dp[i][j][S]<1e9) Q.push((sit){i,j,S,dp[i][j][S]});
		dijkstra(S);
	}
	int ans=1e9;
	for (int i=1;i<=n;i++)
	for (int j=1;j<=m;j++)
		ans=min(ans,dp[i][j][U-1]);
	printf("%d\n",ans);
	return 0;
}