变形的 dijkstra。
先思考什么情况下需要等待以及等待多长时间最优。我们把题目上的计算方法按照当前的时间 \(t\) 和通过所需的时间 \(f(t)\) 列个函数关系:
\[f(t)=t+c+\lfloor \frac{d}{t+1}\rfloor \]然后用 Desmos 画个图可以得到图像(其实就是对勾函数):
因为 \(c,d\geq 0\),所以我们只考虑上半部分。容易发现这个函数是有最值的,根据高一数学知识可得此时 \(t=\sqrt{d}-1\)。
于是我们得到初步结论:跑最短路的时候比较当前时间和上面求出来的东西,如果当前时间已经在其之后,那么根据图象发现等待是不优的,所以正常转移。否则我们直接等到出现最小值的时刻再走就行了。
因为涉及到浮点数运算,所以需要注意精度问题。
一开始的时候发现无解判错了,怎么改都改不过,于是写了个并查集(我好菜)。
标签:abc204,Rush,函数,Hour,题解,ABC204E From: https://www.cnblogs.com/Lydic/p/18431590