SP1700 题解

· · 题解

珂爱的状压 dp。

思路分析

Part 1：为什么是状压 dp？

好好看看题目，完全符合 dp 的特征。

然后再看看数据范围可以发现票最多只有 8 种，并且每一张票只有两种状态：用了与没用。

于是就大致可以确定是状压 dp 了。

Part 2：如何确定的状态？

有了大致确定的思路，我们就可以开始尝试定义状态了。

我们用 0 表示没用过这张票，用 1 表示用过。

不难想到可以这么定义：定义 dp_{i,j,k} 表示当旅行家从城市 i 出发去城市 j 且票的状态为 k 时最少要花多长时间。

然后可以发现起点只可能为 a，于是可以省去第一维。

Part 3：状态的转移？

那我们设 i 为目前终点城市的编号，j 为目前票的状态，k 为上一步的终点城市的编号，p 为从上一步到目前这一步花的票。

于是转移方程如下：

dp[i][j]=min(dp[i][j],dp[k][j^(1<<p)]+G[i][q].dis*1.0/t[p+1]);

Part 4：具体的实现？

那我们不用什么最短路，我们直接用邻接表存图然后循环遍历。

dp[a][0]=0;
for(ri j=1;j<(1<<n);j++){//枚举目前票的状态 
    for(ri p=0;p<n;p++){//枚举上一次花的票 
        if(((j>>p)&1)==0)continue;
        for(ri i=1;i<=m;i++){//枚举票目前的终点城市 
            for(ri q=0;q<G[i].size();q++){//枚举上一次到达的城市在i的邻居中的编号 
                int k=G[i][q].pos;//记录上一次城市编号
                dp[i][j]=min(dp[i][j],dp[k][j^(1<<p)]+G[i][q].dis*1.0/t[p+1]); 
            }
        }
    }   
}

代码

注意多组数据和浮点数即可，也许有注释。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#define ll long long
#define ri register int
using namespace std;
const int MAXN=8;
int n,m,r,a,b,t[10];
double dp[40][1<<MAXN],ans=1e9;
struct node{
    int pos,dis;
};
vector <node> G[40];

void work() {
    ans=1e9;
    for(ri i=1;i<=m;i++){
        G[i].clear();
        for(ri j=0;j<(1<<n);j++)dp[i][j]=1e9;
    }
    for(ri i=1;i<=n;i++)cin>>t[i];
    for(ri i=1;i<=r;i++){
        int u,v,yyhak;
        cin>>u>>v>>yyhak;
        node cur={v,yyhak};
        G[u].push_back(cur);
        node curcur={u,yyhak};
        G[v].push_back(curcur);
    }

    dp[a][0]=0;
    for(ri j=1;j<(1<<n);j++){//枚举目前票的状态 
        for(ri p=0;p<n;p++){//枚举上一次花的票 
            if(((j>>p)&1)==0)continue;
            for(ri i=1;i<=m;i++){//枚举票目前的终点城市 
                for(ri q=0;q<G[i].size();q++){//枚举上一次到达的城市在i的邻居中的编号 
                    int k=G[i][q].pos;//记录上一次城市编号
                    dp[i][j]=min(dp[i][j],dp[k][j^(1<<p)]+G[i][q].dis*1.0/t[p+1]); 
                }
            }
        }
    }

    for(ri i=0;i<(1<<n);i++){
        ans=min(ans,dp[b][i]);
    }
    if(ans==1e9)cout<<"Impossible\n";
    else printf("%.3lf\n",ans);
}

int main() {
    //ios::sync_with_stdio(false);
    while(cin>>n>>m>>r>>a>>b){
        if(n==0&&m==0&&r==0&&a==0&&b==0)return 0;
        work();
    } 
    return 0;
}