早到可以选择停留在原地,所以我们一定会尽早地到达每一个节点,这样一定不劣。
考虑若我们最早可以在 \(t_u\) 时刻到达节点 \(u\),则对于边 \((u,v)\),我们一定会在它最早的解锁时刻由 \(u\) 向 \(v\) 扩展。实现时可以使用 dijkstra,并对每张图的出现时刻用 set 维护,扩展时使用当前边所在图的下一出现时刻转移即可。时间复杂度 \(O(m\log m\log t)\)。
早到可以选择停留在原地,所以我们一定会尽早地到达每一个节点,这样一定不劣。
考虑若我们最早可以在 \(t_u\) 时刻到达节点 \(u\),则对于边 \((u,v)\),我们一定会在它最早的解锁时刻由 \(u\) 向 \(v\) 扩展。实现时可以使用 dijkstra,并对每张图的出现时刻用 set 维护,扩展时使用当前边所在图的下一出现时刻转移即可。时间复杂度 \(O(m\log m\log t)\)。