光玉小镇(bfs建图+状压dp)

题目：光玉小镇
分析：首先将每个电线杆标号，之后bfs建图，建完图后就是道状压dp的模板题了(旅行商问题)。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e12+10;
const int N=205;
typedef pair<int,int> P;
typedef struct Node{
	P point;
	int H;
}Node;
int Next[][2]={{1,0},{-1,0},{0,1},{0,-1}};
int n,m,t,cnt=1;
ll dp[70000][20],d[20][20];
bool book[N][N];
char f[N][N];
map<P,int> M;
bool check(int x,int y){
	
	if(x>=1&&y>=1&&x<=n&&y<=m&&!book[x][y]&&f[x][y]!='#') return true;
	return false;
	
}
ll rec(int s,int v){   //状压dp
	
	if(dp[s][v]>=0){
		return dp[s][v];
	}
	if(s==(1<<(cnt-1))-1&&v==0){
		return dp[s][v]=0;
	}
	ll res=INF;
	for(int i=0;i<cnt-1;i++){
		if(!(s>>i&1)){
			res=min(res,rec(s|1<<i,i)+d[v][i]);
		}
	}
	return dp[s][v]=res;
}
int main(){
	
	P S;
	scanf("%d %d %d",&n,&m,&t);
	for(int i=1;i<=n;i++){   //标号
		scanf("%s",f[i]+1);
		for(int j=1;j<=m;j++){
			if(f[i][j]=='S') S=P(i,j),M[S]=cnt++;
			else if(f[i][j]=='T') M[P(i,j)]=cnt++;
			else M[P(i,j)]=0;
		}
	}

	
	map<P,int>::iterator it;
	fill(d[0],d[0]+20*20,INF);
	for(int i=0;i<=N;i++) d[i][i]=0; 
	for(it=M.begin();it!=M.end();it++){ //bfs建图
		P temp=it->first;
		if(M[temp]==0) continue; 
		queue<Node> que;
		fill(book[0],book[0]+N*N,false);
		que.push((Node){temp,0});
		book[temp.first][temp.second]=true;
		while(!que.empty()){
			
			Node T=que.front(); que.pop();
			P U=T.point;
			for(int i=0;i<4;i++){
			 	int tx=U.first+Next[i][0];
			 	int ty=U.second+Next[i][1];
			 	if(check(tx,ty)){
			 		book[tx][ty]=true;
			 		if(M[P(tx,ty)]!=0) {
			 			if(M[P(tx,ty)]!=1)
			 			d[M[temp]-1][M[P(tx,ty)]-1]=T.H+1+t;
			 			else
			 			d[M[temp]-1][M[P(tx,ty)]-1]=T.H+1;
					 }
			 		que.push((Node){P(tx,ty),T.H+1});
				}
			 }
			 	
		}
	}

	memset(dp,-1,sizeof dp);

	ll sum=rec(0,0);
	if(sum>=INF) printf("-1\n");
	else printf("%lld\n",sum);

	
	
	
	
	return 0;
}