题解：SP1700 TRSTAGE - Traveling by Stagecoach

· · 题解

首先我们发现这题车票数很少。

于是考虑状压 dp，按车票划分状态。

显然地，我们令 dp_{i,j} 表示车票使用状态为二进制下的 i，且行走路径为 a \to j 时所需的最小时间。

易得初始状态：dp_{a,0}=0，答案：\min\{dp_{i,b}\}。

转移时，我们枚举当前点的邻接点 k，以及当前使用的车票 x，得到转移方程：

dp_{i,j}=\min(dp_{i,j},dp_{i \operatorname{xor} 2^j,k}+\frac{w}{t_x})

（w 表示当前点到 k 的边的边权）

直接做即可。code。