드론

모든 요청에서 제한 시간은 최대 $500$이다. 이 값을 $T$라 하자.

먼저 모든 두 거점 $u,v$에 대해 한 번에 이동할 때의 시간 $w(u,v)$와 배터리 $c(u,v)$를 계산한다. 이후 각 출발점 $s$에 대해 확장 그래프에서 최단 경로를 한 번 구한다. 확장 그래프의 정점은 $(v, au)$이며, 이는 총 이동 시간이 정확히 $\tau$인 상태에서 $v$번 거점에 도착해 있음을 의미한다. $\tau+w(u,v) \leq T$이면 $(u, au)$에서 $(v, au+w(u,v))$로 가는 간선을 두고, 이 간선의 비용을 $c(u,v)$로 둔다.

모든 간선 비용은 음수가 아니므로, 출발 상태 $(s,0)$에서 다익스트라 알고리즘을 수행하면 각 상태까지의 최소 배터리 소모를 얻을 수 있다. 다익스트라가 끝난 뒤 각 도착점 $v$와 시간 제한 $t$에 대해

$$\min_{0 \leq \tau \leq t} \operatorname{dist}(v,\tau)$$

를 미리 저장한다. 그러면 각 요청은 $O(1)$에 답할 수 있다.

이 방법은 경로의 이동 시간만 상태에 추가한 것이다. 어떤 실제 경로도 확장 그래프에서는 같은 순서의 상태 이동으로 표현되며, 총 비용은 원래 경로의 소모 배터리와 같다. 반대로 확장 그래프의 모든 경로는 실제 거점 이동 경로에 대응한다. 따라서 확장 그래프에서 얻은 최단 비용은 주어진 시간 이하로 이동하는 실제 경로의 최소 소모 배터리와 같다.

상태 수는 $N(T+1)$이고, 한 상태에서 최대 $N$개의 이동을 시도한다. 각 출발점마다 다익스트라를 수행하므로 전체 시간 복잡도는 $O(N \cdot NT \cdot N \log (NT))$, 즉 $O(N^3T\log(NT))$이다. 주어진 제한에서 충분하다. 저장 공간은 $O(N^2T)$이다.

Solution written by GPT5.5