Tunnels（状压DP模板题）

Problem

求走过所有隧道所需的最小时间。

Solution

隧道总数很小，直接状态压缩。dp(i,j)表示已经走完的状态为i，当前在j所需要的最小时间。首先bfs预处理出不同隧道间的距离，将当前已经走过的隧道压缩成二进制数从小到大枚举状态，枚举每个状态的当前所在隧道，枚举当前隧道所能到达的隧道。

Code

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int inf=1e8;
int n,m,stx[20],sty[20],edx[20],edy[20],mpp[20][20];
int xx[4]={0,0,1,-1},yy[4]={1,-1,0,0},dp[1<<15][20];
char mp[20][20];
bool vis[20][20];
struct node{int x,y,dis;
};
void init()
{memset(mpp,0,sizeof(mpp));for(int i=1;i<=(1<<m)-1;i++)for(int j=1;j<=m;j++)dp[i][j]=inf;for(int i=0;i<m;i++)dp[1<<i][i+1]=0;
}
int bfs(int stxx,int styy,int edxx,int edyy)
{if(stxx==edxx&&styy==edyy) return 0;memset(vis,0,sizeof(vis));queue<node>q;q.push({stxx,styy,0});vis[stxx][styy]=1;while(!q.empty()){node nw=q.front();q.pop();int nx=nw.x,ny=nw.y,dis=nw.dis;for(int i=0;i<4;i++){int vx=nx+xx[i],vy=ny+yy[i];if(vx>=1&&vx<=n&&vy>=1&&vy<=n&&mp[vx][vy]!='#'&&!vis[vx][vy]){if(vx==edxx&&vy==edyy)return dis+1;vis[vx][vy]=1;q.push({vx,vy,dis+1});}}}return inf;
}
int main()
{while(cin>>n>>m){init();for(int i=1;i<=n;i++){getchar();scanf("%s",mp[i]+1);}for(int i=1;i<=m;i++)scanf("%d%d%d%d",&stx[i],&sty[i],&edx[i],&edy[i]);for(int i=1;i<=m;i++){for(int j=1;j<=m;j++){if(j!=i)mpp[i][j]=bfs(edx[i],edy[i],stx[j],sty[j]);}}for(int i=1;i<=(1<<m)-1;i++){for(int j=1;j<=m;j++){int wei=(1<<(j-1));if(i>=wei&&(i&wei)){for(int k=1;k<=m;k++){wei=(1<<(k-1));if(k!=j&&mpp[j][k]<inf&&!(i&wei)){dp[i+wei][k]=min(dp[i+wei][k],dp[i][j]+mpp[j][k]);}}}}}int ans=inf;for(int i=1;i<=m;i++){ans=min(ans,dp[(1<<m)-1][i]);}if(ans<inf)cout<<ans<<endl;elsecout<<-1<<endl;}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！