光玉小镇

看到且‘T’的数目大于等于1并且小于等于15，考虑状压dp可以记录当前修理的状态和最后所在的电线杆，设f[i][j]表示当前集合为i且最后所在的电线杆为j的代价，先预处理家与电线杆之间的距离和两两电线杆之间的距离，并转移即可

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define int long long
using namespace std;
const int INF=0x3f3f3f3f;
int read()
{
    int s=0,bj=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')bj|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
    return bj?-s:s;
}
void printnum(int x)
{
    if(x>9)printnum(x/10);
    putchar(x%10^48);
}
void print(int x,char ch)
{
    if(x<0){putchar('-');x=-x;}
    printnum(x);putchar(ch);
}
int n,m,t;
char ch[205][205];
bool vst[205][205];
struct node
{
    int x,y;
    bool operator < (const node &a) const {return x==a.x?y<a.y:x<a.x;}
}s,num[16];int cnt;
int f[1<<15][16],dis[16],d[16][16];
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
int ans=0x3f3f3f3f;
int Get(node S,node T)
{
    node tmp,ret;int nx,ny;
    memset(vst,0,sizeof(vst));
    priority_queue<pair<int,node> >q;
    vst[S.x][S.y]=1;q.push(make_pair(0,S));
    while(!q.empty())
    {
        int no=-q.top().first;tmp=q.top().second;q.pop();
        for(int i=0;i<4;++i)
        {
            nx=tmp.x+dx[i];ny=tmp.y+dy[i];
            if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&!vst[nx][ny]&&(ch[nx][ny]^'#'))
            {
                if(nx==T.x&&ny==T.y)return no+1;
                vst[nx][ny]=1;ret.x=nx;ret.y=ny;q.push(make_pair(-no-1,ret));
            }
        }
    }
    return INF;
}//搜索计算距离 
signed main()
{
    n=read();m=read();t=read();
    memset(f,0x3f,sizeof(f));
    for(int i=1;i<=n;++i)
    {
        scanf("%s",ch[i]+1);
        for(int j=1;j<=m;++j)
        {
            if(ch[i][j]=='S'){s.x=i;s.y=j;}
            else if(ch[i][j]=='T'){num[cnt].x=i;num[cnt].y=j;++cnt;}
        }
    }//记录家，电线杆的坐标 
    for(int i=0;i<cnt;++i)
    {
        f[1<<i][i]=dis[i]=Get(s,num[i]);
        if(dis[i]==INF){print(-1,'\n');return 0;}
        for(int j=i+1;j<cnt;++j)d[i][j]=d[j][i]=Get(num[i],num[j]);
    }//预处理距离 
    for(int i=0;i<(1<<cnt);++i)
    for(int j=0;j<cnt;++j)
    if((1<<j)&i)//在i集合中存在j 
    {
        for(int k=0;k<cnt;++k)
        if(!((1<<k)&i))//在i集合内没有k，才能转移 
        f[(1<<k)|i][k]=min(f[(1<<k)|i][k],f[i][j]+d[j][k]);//由j走到k 
    }
    for(int i=0;i<cnt;++i)ans=min(ans,f[(1<<cnt)-1][i]+dis[i]);//对于每一个结束的电线杆取min 
    print(ans+cnt*t,'\n');//最后一起加上修理的时间 
    return 0;
}