分析

对于这张图的关键点非常少，对于每一个点对我们可以求出之间的距离，我们考虑状压转移。 ，表示节点 为根节点，已经走过的节点集合为 所需要的最小步数。总的复杂度为 ， 表示有多少个坏掉的电线杆。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 210,inf = 0x3f3f3f3f;
#define LL long long
struct Node{int x,y;}p[21];
int vis[N][N];
int dp[N][101000];int n,m,t,top,f[21][21];
char ch[N][N];
int dx[4] = {0,0,-1,1},dy[4] = {1,-1,0,0};
void solve(int id) {
    memset(vis,inf,sizeof(vis));vis[p[id].x][p[id].y] = 0;
    queue<Node> q;q.push((Node){p[id].x,p[id].y});
    while(q.size()) {
        Node x = q.front();q.pop();
        for(int i = 0;i < 4;i++) {
            int X = x.x + dx[i],Y = x.y + dy[i];
            if(vis[X][Y] != inf||X < 1||Y < 1||X > n||Y > m||ch[X][Y] == '#') continue;
            vis[X][Y] = vis[x.x][x.y] + 1;
            q.push((Node){X,Y});
        }
    }
}
int main()
{
    cin >> n >> m >> t;
    int sx,sy;
    for(int i = 1;i <= n;i++) {
        for(int j = 1;j <= m;j++) {
            cin >> ch[i][j];
            if(ch[i][j] == 'S') sx = i,sy = j;
            if(ch[i][j] == 'T') p[++top] = (Node){i,j};
        }
    }
    p[++top] = (Node){sx,sy};
    for(int i = 1;i <= top;i++) {
        solve(i);
        for(int j = 1;j <= top;j++) {
            f[i][j] = vis[p[j].x][p[j].y];
        }
    }
    memset(dp,0x3f,sizeof(dp));
    dp[top][1<<top-1] = 0;
    for(int s = 1;s < (1<<top);s++) {
        for(int j = 1;j <= top;j++) {
            if(((s>>j-1)&1) && dp[j][s] != inf) {
                for(int i = 1;i <= top;i++) {
                    if((s>>i-1)&1) continue;
                    dp[i][(s|(1<<i-1))] = min(dp[j][s] + f[j][i],dp[i][s|(1<<i-1)]);
                }
            }
        }
    }
    int ans = inf;
    for(int i = 1;i <= top;i++) ans = min(ans,dp[i][(1<<top)-1] + f[i][top]);
    if(ans == inf) cout << "-1" << endl;
    else cout << ans + 1LL * (top-1) * t << endl;
    return 0;
}