题解：AT_abc204_e [ABC204E] Rush Hour 2

变形的 dijkstra。

先思考什么情况下需要等待以及等待多长时间最优。我们把题目上的计算方法按照当前的时间 \(t\) 和通过所需的时间 \(f(t)\) 列个函数关系：

\[f(t)=t+c+\lfloor \frac{d}{t+1}\rfloor \]

然后用 Desmos 画个图可以得到图像（其实就是对勾函数）：

因为 \(c,d\geq 0\)，所以我们只考虑上半部分。容易发现这个函数是有最值的，根据高一数学知识可得此时 \(t=\sqrt{d}-1\)。

于是我们得到初步结论：跑最短路的时候比较当前时间和上面求出来的东西，如果当前时间已经在其之后，那么根据图象发现等待是不优的，所以正常转移。否则我们直接等到出现最小值的时刻再走就行了。

因为涉及到浮点数运算，所以需要注意精度问题。

一开始的时候发现无解判错了，怎么改都改不过，于是写了个并查集（我好菜）。

提交记录