题解：SP1700 TRSTAGE - Traveling by Stagecoach

__Deng_Rui_Song__ · 2024-09-27 09:45:29 · 题解

可怕的状压dp

咳咳，言归正传

problem

传送门

题意已经很清楚了，我就不再叙述一遍了

solution

Q1：为啥是状压 dp？

A1：看看数据范围：票和城市很小，并且都只有两种状态，符合状压 dp 性质，接下来 dp 四步走。

Q2：dp 状态是什么？

A2：状压城市有点不现实，但是可以状压票，不难想到设 dp_{i,j} 表示票的状态为 i，当前城市为 j 的最短时间。

Q3：答案是什么？

A3：由于最后票的状态不确定，所以当然是 \min_{i=0}^{2^n-1}dp_{i,b}。

Q4：dp 转移怎么写？

A4：枚举上一个城市 k 和上一个用的票 x，城市 k 和当前城市 j 之间必须存在一条边（超巨的你：废话），票 x 在状态 i 里必须为 1（超巨的你：又一句废话），城市 k 到城市 j 的时间为 \frac{g_{k,j}}{t_x}，因此转移方程为：dp_{i,j} = \min\{dp_{i,j},dp_{i\oplus2^x,last} + \frac{g_{j,k}}{a_x}\}。

Q5：初始化？

A5：很明显，dp_{0,a}=0，其余设 +\infty，dp 四步走结束。

Q6：怎么实现？

A6：可以用邻接矩阵，邻接表，链式前向星存图，我用的是邻接表存图。

code

#include<bits/stdc++.h>
using namespace std;
struct node{int v,w;};
int n,m,p,a,b,t[8];
double dp[256][35];
vector<node> g[35];
void solve(){
    for (int i = 0; i < n; i++) cin >> t[i];
    while (p--){
        int x,y,w;
        cin >> x >> y >> w;
        g[x].push_back({y,w});
        g[y].push_back({x,w});
    }
    for (int i = 0; i < 1 << n; i++) for (int j = 1; j <= m; j++) dp[i][j] = 1e9;
    dp[0][a] = 0;//初始化
    for (int i = 1; i < 1 << n; i++)//票的状态
        for (int j = 1; j <= m; j++)//当前城市
            for (int k = 0; k < g[j].size(); k++)//上一个城市
                for (int x = 0; x < n; x++)//上一个用的票
                    if (i >> x & 1)//如果用了这个票
                        dp[i][j] = min(dp[i][j],dp[i ^ 1 << x][g[j][k].v] + g[j][k].w * 1.0 / t[x]);//转移
    double ans = 1e9;
    for (int i = 0; i < (1 << n); i++) ans = min(ans,dp[i][b]);//答案
    (ans == 1e9 ? cout << "Impossible\n" : cout << fixed << setprecision(3) << ans << '\n');
    for (int i = 1; i <= m; i++) g[i].clear();//多测不清空，爆零两行泪
}
int main(){
    while (cin >> n >> m >> p >> a >> b){
        if (!n) return 0;
        solve();
    }
    return 0;
}