NC6874C-光玉小镇

NC6874C-光玉小镇

求从走完所有再回到所需的最小时间为多少，每经过一次T时间需要停，走一步的时间是.
若不能走完所有的，输出，否则输出所需的最小时间。

Solution

状压DP+BFS
难点：有多个，我们需要先确定的顺序。

注意到的范围，我们从状压DP的经典题TSP问题中得到启示，我们可以用状压DP来枚举每一种可能的顺序，因为题目本身不是让我们求顺序，而是让我们求最优顺序下的结果。

状态：表示当前在状态下最后一个走的是第个的最小花费。
（这里的花费是不包含停下来的时间，因为停下来的时间可以最后算答案的时候直接加上）

表示从到的距离。

转移式：
初始化:

上式中出现了距离，所以我们需要写一个BFS来求某两点之间的距离，如果存在走不到，我们返回表示走不完所有的。

复杂度：

：状压的时候将点数前移一个从0开始更为方便。

Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF = 0x3f3f3f3f;
const ll mod  = 1e9 + 7;
const ll N = 2e2 + 5;

struct node{
    int x,y,z;
}Q[N*N];

int n,m,sx,sy,cnt,dis[20],e[20][20],f[1<<16][20];
ll t,ans=1e18;
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1,};
bool vis[N][N];
char s[N][N];

vector<pii> V;

int BFS(int sx,int sy,int ex,int ey){
    memset(vis,false,sizeof(vis));
    queue<node> q;
    vis[sx][sy]=true;
    q.push({sx,sy,0});
    while(!q.empty()){
        node t=q.front();
        q.pop();
        if(t.x==ex && t.y==ey) return t.z;
        for(int i=0;i<4;i++){
            int nx=t.x+dx[i];
            int ny=t.y+dy[i];
            int nz=t.z+1;
            if(nx<0 || nx>=n || ny<0 || ny>=m || vis[nx][ny] || s[nx][ny]=='#') continue;
            vis[nx][ny]=true;
            q.push({nx,ny,nz});
        }
    }
    return -1;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m>>t;
    memset(f,0x3f,sizeof(f));
    for(int i=0;i<n;i++) cin>>s[i];
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            if(s[i][j]=='S') sx=i,sy=j;
            else if(s[i][j]=='T') V.emplace_back(i,j);

    cnt=V.size();
    for(int i=0;i<cnt;i++){
        f[1<<i][i]=dis[i]=BFS(sx,sy,V[i].fi,V[i].se);
        if(dis[i]==-1) return cout<<-1<<'\n',0;
    }

    for(int i=0;i<cnt;i++)
        for(int j=i+1;j<cnt;j++)
            e[i][j]=e[j][i]=BFS(V[i].fi,V[i].se,V[j].fi,V[j].se);

    for(int i=0;i<(1<<cnt);i++)
        for(int j=0;j<cnt;j++)
            if((1<<j)&i) for(int k=0;k<cnt;k++)
                if(!((1<<k)&i)) f[i|1<<k][k]=min(f[i|1<<k][k],f[i][j]+e[j][k]);

    for(int i=0;i<cnt;i++) ans=min(ans,f[(1<<cnt)-1][i]+dis[i]+t*cnt);
    cout<<ans<<'\n';
    return 0;
}