题目分析

该问题是一个带状态约束的最短路径问题。旅行者需从起点城市（a）到达终点城市（b），在道路网络中使用有限的车票（每张票指定马匹数）以最小化总旅行时间。关键约束包括：

• 道路网络：m个城市（节点），p条双向道路（边），每条道路有固定距离。
• 车票限制：n张车票（1 ≤ n ≤ 8），每张票的马匹数t_i决定速度（时间 = 距离 / 马匹数），每张票仅能用一次。
• 换乘规则：每次移动（城市间直达）必须使用一张车票，且到达城市后必须换乘（更换马车）。

目标是在车票使用组合与路径选择的双重约束下，找到从起点到终点的最短时间路径。若路径不存在或车票不足，输出Impossible。

解题思路：状态压缩动态规划（DP）

由于车票数量n较小（≤8），但城市数m可能较大（≤30），适合采用状态压缩DP。其核心是将车票使用状态编码为二进制位掩码，从而高效枚举所有车票组合与路径的交互。

1. 状态定义

• 状态表示：dp[state][u]表示使用车票状态为state（二进制整数，第k位为1表示第k张票已使用）时，到达城市u的最小时间。
• 状态维度：
  • state范围：0 到 (1 << n) - 1（共2^n种状态）。
  • u范围：1 到 m（城市编号）。
• 初始化：
  • dp[0][src] = 0：未使用任何车票时，起点时间为0。
  • 其余状态初始化为INF（极大值）。

2. 状态转移

对每个状态state和当前城市u，尝试所有未使用的车票和从u出发的道路，更新相邻城市的时间：

for 每个状态 state:
  for 当前城市 u:
    for 每个未使用车票 k（state 的第 k 位为 0）:
      for 每条从 u 到 v 的道路（距离 w）:
        新状态 new_state = state | (1 << k)
        新时间 = dp[state][u] + w / t_k  # t_k 是车票 k 的马匹数
        若新时间 < dp[new_state][v]，则更新 dp[new_state][v]

3. 结果获取

所有状态中，终点des的最小时间即为答案：

res = min{ dp[state][des] } for all state

若res仍为INF，输出Impossible。

4. 算法优化

• 状态枚举顺序：从小到大枚举状态state，确保子状态先被计算。
• 图存储：使用邻接表g[u]存储从城市u出发的所有边（pair<v, w>），加速边遍历。
• 时间复杂度：O(2^n * m * n * m)，因n≤8、m≤30，最大计算量约2^8 * 30 * 8 * 30 ≈ 1.8e6，可接受。

代码示例

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
#define MAXN 2222
#define INF 1000000007
using namespace std;
double dp[333][33];
typedef pair<int, int> P;
vector<P>g[33];
int t, n, m, src, des;
int num[33];
int main()
{
    int u, v, w;
    while (scanf("%d%d%d%d%d", &t, &n, &m, &src, &des) != EOF)
    {
        if (!t && !n && !m && !src && !des) break;
        for (int i = 0; i < t; i++) scanf("%d", &num[i]);
        for (int i = 0; i <= n; i++) g[i].clear();
        for (int i = 0; i < m; i++)
        {
            scanf("%d%d%d", &u, &v, &w);
            g[u].push_back(make_pair(v, w));
            g[v].push_back(make_pair(u, w));
        }
        for (int i = 0; i <= 300; i++)
            for (int j = 0; j < 33; j++)
                dp[i][j] = INF;
        dp[0][src] = 0;
        double res = INF;
        for (int i = 0; i < (1 << t); i++)
        {
            for (u = 1; u <= n; u++)
                for (int k = 0; k < t; k++)
                    if (!(i & (1 << k)))
                    {
                        for (int j = 0; j < g[u].size(); j++)
                        {
                            v = g[u][j].first;
                            w = g[u][j].second;
                            dp[i | (1 << k)][v] = min(dp[i | (1 << k)][v], dp[i][u] + (double)w / num[k]);
                        }
                    }
            res = min(res, dp[i][des]);
        }
        if (res == INF) puts("Impossible");
        else printf("%.3f\n", res);

    }
    return 0;
}

关键问题与处理

1. 车票与路径的耦合
   车票影响移动速度，且每张票仅用一次。状态压缩DP通过二进制状态精确控制车票使用顺序，避免重复使用。

2. 不可达情况处理

   • 道路不连通：若从起点无法到达终点，所有状态dp[state][des]均为INF。
   • 车票不足：即使道路连通，若车票组合无法覆盖路径长度，仍不可达。

3. 浮点数精度
   时间计算为w / t_k（浮点数）。题目要求误差≤0.001，代码用double存储并输出三位小数（%.3f）满足要求。

4. 重边处理
   城市间可能存在多条道路（输入未保证无重边），代码使用邻接表存储所有边，确保最优选择。