C++14(g++5.4) 解法, 执行用时: 62ms, 内存消耗: 608K, 提交时间: 2018-12-27 16:27:32

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int T;
int n,m;
char s[105][105];
int vis[105][105];
struct node{
	int x,y,step;
	node(int t1,int t2,int t3){
		x=t1,y=t2,step=t3;
	}
};
int dx[10]={0,0,1,-1};
int dy[10]={1,-1,0,0};
int check(int x,int y){
	if(x<1||x>n||y<1||y>m)return 0;
	return 1;
}
int bfs(int sx,int sy,int ex,int ey,int v,int tp){
	queue<node>q;
	q.push(node(sx,sy,0));
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			vis[i][j]=0;
		}
	}
	while(!q.empty()){
		node cur=q.front();q.pop();
		if(cur.x==ex&&cur.y==ey)return cur.step;
		for(int i=0;i<4;i++){
			int nx=cur.x+dx[i];
			int ny=cur.y+dy[i];
			if(!check(nx,ny)||vis[nx][ny])continue;
			if(!tp&&s[nx][ny]=='#')continue;
			vis[nx][ny]=1;
			q.push(node(nx,ny,cur.step+v));
		}
	}
	return 1e8;
}
int x[5],y[5],c[5],v[5],ans;
void dfs(int time,int sx,int sy,int res,int sum){
	if(time==4){
		res+=bfs(sx,sy,x[4],y[4],sum,0);
		ans=min(ans,res);
		return;
	}
	for(int i=1;i<=3;i++){
		if(!c[i]){
			c[i]=1;
			int tmp=res+bfs(sx,sy,x[i],y[i],sum,1);
			dfs(time+1,x[i],y[i],tmp,max(sum,v[i]+1));
			c[i]=0;
		}
	}
}
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++){
			scanf("%s",s[i]+1);
			for(int j=1;j<=m;j++){
				if(s[i][j]=='S'){
					x[0]=i,y[0]=j;
				}
				if(s[i][j]=='X'){
					x[1]=i,y[1]=j;
				}
				if(s[i][j]=='Y'){
					x[2]=i,y[2]=j;
				}
				if(s[i][j]=='Z'){
					x[3]=i,y[3]=j;
				}
				if(s[i][j]=='E'){
					x[4]=i,y[4]=j;
				}
			}
		}
		for(int i=1;i<=3;i++){
			scanf("%d",&v[i]);
		}
		ans=1e8;
		dfs(1,x[0],y[0],0,1);
		printf("%d\n",ans);
	}
}

C++11(clang++ 3.9) 解法, 执行用时: 56ms, 内存消耗: 352K, 提交时间: 2018-12-23 16:05:17

#include<bits/stdc++.h>
using namespace std;
struct node
{
	int x,y,step;
	node(int t1,int t2,int t3)
	{
		x=t1,y=t2,step=t3;
	}
};
char s[105][105];
int vis[105][105],n,m;
int mv[4][2]={1,0,-1,0,0,1,0,-1};

bool check(int x,int y)
{
	if(x<1||x>n||y<1||y>m)return 0;
	return 1;
}
int bfs(int sx,int sy,int tx,int ty,int v,int tp)
{
	queue<node>q;
	q.push(node(sx,sy,0));
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)vis[i][j]=0;
	while(!q.empty())
	{
		node e=q.front();q.pop();
		if(e.x==tx&&e.y==ty)
		return e.step;
		for(int i=0;i<4;i++)
		{
			int xx=e.x+mv[i][0];
			int yy=e.y+mv[i][1];
			
			if(!check(xx,yy)||vis[xx][yy])continue;
			if(!tp&&s[xx][yy]=='#')continue;
			
			vis[xx][yy]=1;
			q.push(node(xx,yy,e.step+v));
		}
	}
	return 1e8;
}
int x[5],y[5],ans,c[5],v[5];
void dfs(int time,int sx,int sy,int res,int sum)
{
	if(time==4)
	{
		res+=bfs(sx,sy,x[4],y[4],sum,0);
		ans=min(ans,res);
		return;
	}
	for(int i=1;i<=3;i++)
	if(!c[i])
	{
		c[i]=1;
		int tmp=res+bfs(sx,sy,x[i],y[i],sum,1);
		dfs(time+1,x[i],y[i],tmp,max(sum,v[i]+1));
		c[i]=0;
	}
}
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		cin>>n>>m;
		for(int i=1;i<=n;i++)
		{
			scanf("%s",s[i]+1);
			for(int j=1;j<=m;j++)
			if(s[i][j]=='S')
			x[0]=i,y[0]=j;
			else if(s[i][j]=='X')
			x[1]=i,y[1]=j;
			else if(s[i][j]=='Y')
			x[2]=i,y[2]=j;
			else if(s[i][j]=='Z')
			x[3]=i,y[3]=j;
			else if(s[i][j]=='E')
			x[4]=i,y[4]=j;
		}
		for(int i=1;i<=3;i++)scanf("%d",&v[i]);
		ans=1e8;
		dfs(1,x[0],y[0],0,1);
		printf("%d\n",ans);
	}
	return 0;
}