记录编号	126367	评测结果	AAAAAAAAAA
题目名称	[WC 2008]游览计划	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.067 s
提交时间	2014-10-12 09:47:05	内存使用	1.20 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
using namespace std;
const int SIZEn=15,SIZEK=15,SIZEN=110,INF=0x7fffffff/2;
int n,m,K;
int board[SIZEn][SIZEn]={0};
int spotx[SIZEK]={0},spoty[SIZEK]={0};
int f[SIZEn][SIZEn][1025]={0};
int hash(int i,int j){
	return i*m+j;
}
int N,S;
vector<pair<int,int> > c[SIZEN];
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
void addedge(int a,int b,int w){
	c[a].push_back(make_pair(b,w));
}
void makegraph(void){
	N=n*m;
	S=N;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			for(int d=0;d<4;d++){
				int i1=i+dx[d],j1=j+dy[d];
				if(i1<0||i1>=n||j1<0||j1>=m) continue;
				addedge(hash(i,j),hash(i1,j1),board[i1][j1]);
			}
		}
	}
	for(int i=0;i<N;i++) addedge(S,i,0);
}
int dis[SIZEN]={0};
bool inq[SIZEN]={0};
queue<int> Q;
void SPFA(void){
	memset(inq,0,sizeof(inq));
	for(int i=0;i<=N;i++) dis[i]=INF;
	dis[S]=0;inq[S]=true;Q.push(S);
	while(!Q.empty()){
		int x=Q.front();Q.pop();inq[x]=false;
		for(int i=0;i<c[x].size();i++){
			int u=c[x][i].first;
			if(dis[x]+c[x][i].second<dis[u]){
				dis[u]=dis[x]+c[x][i].second;
				if(!inq[u]){
					inq[u]=true;
					Q.push(u);
				}
			}
		}
	}
}
void work(void){
	for(int i=0;i<SIZEn;i++)
		for(int j=0;j<SIZEn;j++)
			for(int k=0;k<1025;k++) f[i][j][k]=INF;
	for(int i=0;i<K;i++) f[spotx[i]][spoty[i]][1<<i]=0;
	for(int s=1;s<(1<<K);s++){
		//先试图用两个凑起来
		for(int i=0;i<n;i++)
			for(int j=0;j<m;j++)
				for(int t=s;t;t=(t-1)&s)
					f[i][j][s]=min(f[i][j][s],f[i][j][t]+f[i][j][s-t]-board[i][j]);
		//下面更新超级源到各点的边权
		int k=0;
		for(int i=0;i<n;i++)
			for(int j=0;j<m;j++)
				c[S][k++].second=f[i][j][s];
		SPFA();
		//然后用最短路更新一次
		k=0;
		for(int i=0;i<n;i++)
			for(int j=0;j<m;j++)
				f[i][j][s]=min(f[i][j][s],dis[k++]);
	}
	int ans=INF;
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++) ans=min(ans,f[i][j][(1<<K)-1]);
	printf("%d\n",ans);
}
void read(void){
	K=0;
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			scanf("%d",&board[i][j]);
			if(!board[i][j]) spotx[K]=i,spoty[K]=j,K++;
		}
	}
}
int main(){
	freopen("wc2008_trip.in","r",stdin);
	freopen("wc2008_trip.out","w",stdout);
	read();
	makegraph();
	work();
	return 0;
}