AT_abc192_e [ABC192E] Train 题解

· · 题解

分析

模板题。

跑一个最短路就行了。定义 \mathit{dis}_{i} 表示从 x 出发到达 i 时的最早时间。那么经过 u \to v 这条边时，到 v 的最早时间就是 \mathit{dis}_u+(k_i-(\mathit{dis}_{u}\bmod k_i))\bmod k_i +t_i。

代码

Link.