C++14(g++5.4) 解法, 执行用时: 90ms, 内存消耗: 23128K, 提交时间: 2020-08-22 20:51:16

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=509;
int vis[maxn][maxn],inf;
int n,m,t,x[maxn],y[maxn],dis[maxn][maxn],top=1,ha[maxn][maxn];
int dp[1<<17][18];
char a[maxn][maxn];
struct p{
	int x,y,steps;
};
int qq[5]={0,0,1,-1},ww[5]={1,-1,0,0};
void bfs(int index )
{
	queue<p>q;
	q.push( (p){x[index],y[index],0} );
	memset(vis,0,sizeof(vis));
	vis[ x[index] ][ y[index] ]=1;
	while( !q.empty() )
	{
		p now=q.front(); q.pop();
		for(int i=0;i<4;i++)
		{
			int nx=now.x+qq[i],ny=now.y+ww[i];
			if( nx<1||nx>n||ny<1||ny>m||vis[nx][ny] )	continue;
			if( a[nx][ny]=='#' )	continue;
			vis[nx][ny]=1;
			if( ha[nx][ny] )	dis[index][ ha[nx][ny] ]=now.steps+1;
			q.push( (p){nx,ny,now.steps+1} );
		}
	}
}
void over()
{
	for(int i=2;i<=top;i++)
		if( dis[1][i]==inf )
		{
			cout << -1;
			exit(0);
		}
}
signed main()
{
	cin >> n >> m >> t;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	{
		cin >> a[i][j];
		if( a[i][j]=='T' )	x[++top]=i,y[top]=j,ha[i][j]=top;
		else if( a[i][j]=='S' )	x[1]=i,y[1]=j,ha[i][j]=1;
	}
	memset(dp,127,sizeof(dp));
	memset(dis,127,sizeof(dis));
	inf=dp[0][0];
	for(int i=1;i<=top;i++)	dis[i][i]=0;
	for(int i=1;i<=top;i++)	bfs(i);
	dp[1][1]=0;
	over();
	for(int i=2;i<(1<<top);i++)
	for(int j=1;j<=top;j++)
	{
		if( i&(1<<(j-1)) )
		{
			for(int q=1;q<=top;q++)
			{
				if( q==j )	continue;
				if( i&(1<<(q-1)) )
				{
					int last = (i^( 1<<(j-1) ) );
					dp[i][j]=min( dp[i][j],dp[last][q]+dis[q][j] ); 
				}
			}
		}
	}
	int ans=inf;
	for(int i=1;i<=top;i++)
		ans=min( ans,dp[(1<<top)-1][i]+dis[i][1] );
	cout << ans+(top-1)*t;
}

C++(clang++11) 解法, 执行用时: 47ms, 内存消耗: 4728K, 提交时间: 2021-02-05 17:25:59

#include <iostream>
#include <queue>
using namespace std;
char a[205][205];
int dis[205][205],fx[5]={0,0,1,-1},fy[5]={1,-1,0,0},p,w[20][20],dp[16][100005];
queue <pair<int,int> > q;
int main(int argc, char** argv) {
	int n,m,t;
	cin >> n >> m >> t;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin >> a[i][j];
	int cnt=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(a[i][j]=='S'||a[i][j]=='T')
			{
				if(a[i][j]=='S') p=cnt;
				for(int k=1;k<=n;k++) for(int l=1;l<=m;l++) dis[k][l]=1e9;
				q.push({i,j}),dis[i][j]=0;
				while(!q.empty())
				{
					int x=q.front().first,y=q.front().second;
					q.pop();
					for(int f=0;f<4;f++)
					{
						int nx=x+fx[f],ny=y+fy[f];
						if(a[nx][ny]!='#'&&dis[nx][ny]>dis[x][y]+1)
							dis[nx][ny]=dis[x][y]+1,q.push({nx,ny});
					}
				}
				int now=0;
				for(int k=1;k<=n;k++) for(int l=1;l<=m;l++)
					if(a[k][l]=='S'||a[k][l]=='T') w[cnt][now++]=dis[k][l];
				++cnt;
			}
		}
	}; 
	for(int i=0;i<cnt;i++)
		for(int j=0;j<(1<<cnt);j++) dp[i][j]=1e9;
	w[p][p]=1e9,dp[p][0]=0;
	for(int i=0;i<(1<<cnt);i++)
	{
		for(int j=0;j<cnt;j++)
		{
			for(int k=0;k<cnt;k++)
				dp[k][(1<<k)|i]=min(dp[k][(1<<k)|i],dp[j][i]+w[j][k]);
		}
	}
    if(dp[p][(1<<cnt)-1]>5e8)
    {
        puts("-1");
        return 0;
    }
	cout << dp[p][(1<<cnt)-1]+(long long)t*(cnt-1);
	return 0;
}