CF553E Kyoya and Train 做题记录

给定一张 $n$ 个点 $m$ 条边的无重边无自环的有向图，你要从 $1$ 号点到 $n$ 号点去。

如果你在 $t$ 时刻之后到达 $n$ 号点，你要交 $x$ 元的罚款。

每条边从 $a_i$ 到 $b_i$，走过它需要花费 $c_i$ 元，多次走过同一条边需要多次花费。

走过每条边所需的时间是随机的，对于 $k \in [1,t]$，$\frac{p_{i,k}}{10^5}$ 表示走过第 $i$ 条边需要时间 $k$ 的概率。因此如果多次走过同一条边，所需的时间也可能不同。

你希望花费尽可能少的钱（花费与罚款之和）到达 $n$ 号点，因此每到达一个点，你可能会更改原有的计划。

求在最优决策下，你期望花费的钱数。

$n \le 50$，$m \le 100$，$t \le 2 \times 10^4$，$x,c_i \le 10^6$，$\sum_{k=1}^t p_{i,k} = 10^5$，答案精度误差 $\le 10^{-6}$。

首先设 $dp_{i,j}$ 表示在 $j$ 时刻开始，从 $i$ 走到 $n$ 的最小花费，那么有：

$\begin{cases}dp_{n,i}=0&i\le t\\dp_{n,i}=x&i>t\\dp_{u,i}=\min\limits_{\text{u -- j -> v}}c_j+\sum\limits_{k=1}^t \dfrac{p_{j,k}}{10^5}dp_{v,i+k}&u\not=n,i\le t\\dp_{u,i}=\operatorname{dist}(u,n)+x&u\not=n,i>t\end{cases}$

其中 $\operatorname{dist}(x,y)$ 表示从 $x$ 到 $y$ 的最小花费（路程上的，不算罚款），我们最后需要 $dp_{1,0}$。

由于这不一定是 DAG 而且 dijkstra 不好写所以需要 spfa，然而暴力跑 spfa 是 $O(nmt^2)$ 的，显然不够优。

容易发现，令人讨厌的转移部分显然是 $\sum\limits_{k=1}^t \dfrac{p_{j,k}}{10^5}dp_{v,i+k}$，考虑优化这一部分。

令 $p’_{j,t-k}=\dfrac{p_{j,k}}{10^5}$，那么原式可化为：

$\sum\limits_{k=1}^t p'_{j,t-k}dp_{v,i+k}$

容易发现这是一个卷积的形式，下标和恒为 $t-k+i+k=i+t$，那么式子就变成了：

$(p_j'*dp_v)_{i+t}$

所以优化后的转移为：

$\begin{cases}dp_{n,i}=0&i\le t\\dp_{n,i}=x&i>t\\dp_{u,i}=\min\limits_{\text{u -- j -> v}}c_j+(p_j'*dp_v)_{i+t}&u\not=n,i\le t\\dp_{u,i}=\operatorname{dist}(u,n)+x&u\not=n,i>t\end{cases}$

跑 spfa 的话时间复杂度为 $O(nmt\log t)$，但是跑不满，而且有 8S，所以足够通过此题。

spfa 在反向图上跑即可，相当于倒着转移吧。