题目描述
经历过与妻儿生离死别的牛牛，选择成为一名电工，过上平淡的日子。牛牛每天的工作是从家里出发，修理完小镇上所有坏掉的电线杆，然后回家和家人团聚。已知小镇是个n\times mn×m的区域，每块格子的类型有以下几种：

‘.’：表示该地点为空地。

‘#’：表示该地点正在施工，牛牛无法移动到该地点。

‘S’：表示牛牛的家。

‘T’：表示此处有一个坏掉的电线杆。

牛牛每秒可以往上/下/左/右四个方向移动一格，且牛牛修理一个电线杆所花的时间为tt秒，请问牛牛从家里出发修理完电线杆并最后回到家的最短时间是多少？
思路：因为电线杆的数量比较小，所以我们可以用状压来解决它。首先搜索求出电线杆和出发点和家的最短路。dp一维表示状态，第二维表示最后到达的点，然后递推公式就很简单了，枚举没走的所有电线杆，更新答案就行了。
代码：

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int n,m,t,dir[4][2]={1,0,-1,0,0,1,0,-1};
char ch[220][220];
int id[220][220],dist[20][20],dist1[220][220];
struct Node{
    int x,y;
    Node(int xx,int yy):x(xx),y(yy){}
};
const int inf=0x3f3f3f3f;
void solve(int si,int sj,int p)
{
    //printf("%d\n",p);
    memset(dist1,inf,sizeof(dist1));
    dist1[si][sj]=0;
    queue<Node>q;
    q.push(Node(si,sj));
    while(!q.empty()){
        int x=q.front().x,y=q.front().y;
        q.pop();
        for(int i=0;i<4;i++){
            int xx=x+dir[i][0],yy=y+dir[i][1];
            if(xx<=n-1&&xx>=0&&yy<=m-1&&yy>=0){
                if(ch[xx][yy]=='#')continue;
                if(dist1[xx][yy]>dist1[x][y]+1){
                    dist1[xx][yy]=dist1[x][y]+1;
                    if(id[xx][yy])dist[p][id[xx][yy]]=dist1[xx][yy];
                    q.push(Node(xx,yy));
                }
            }
        }
    }
}
int dp[1<<17][20];
int main()
{
    scanf("%d%d%d",&n,&m,&t);
    for(int i=0;i<n;i++)
        scanf("%s",ch[i]);
    int st,cnt=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            //printf("%d\n",cnt);
            if(ch[i][j]=='S')
                id[i][j]=++cnt,st=cnt;//printf("%d\n",cnt);
            else if(ch[i][j]=='T')
                id[i][j]=++cnt;
        }
    }

    memset(dist,0x3f3f3f3f,sizeof(dist));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(ch[i][j]=='S'||ch[i][j]=='T'){
                solve(i,j,id[i][j]),dist[id[i][j]][id[i][j]]=0;
            }
        }
    }
    memset(dp,inf,sizeof(dp));
    dp[1<<(st-1)][st]=0;
    for(int i=1<<(st-1);i<1<<cnt;i++){
        for(int k=1;k<=cnt;k++){
            if((1<<(k-1)&i)==0)continue;
            for(int j=1;j<=cnt;j++){
                if(1<<(j-1)&i)continue;
                dp[i|(1<<(j-1))][j]=min(dp[i|(1<<(j-1))][j],dp[i][k]+dist[k][j]);
                //printf("%d %d %d %d %d %d\n",i|(1<<(j-1)),dp[i|(1<<(j-1))][j],i,k,dp[i][k],dist[k][j]);
            }
        }
    }
    int ans=0x3f3f3f3f;
    for(int i=1;i<=cnt;i++){
        ans=min(ans,dp[(1<<cnt)-1][i]+dist[i][st]);
    }
    if(ans==0x3f3f3f3f)printf("-1\n");
    else printf("%lld\n",(long long)(ans+(long long)t*(cnt-1)));
    return 0;
}