[BOJ 8249] Dookoła świata

문제: https://www.acmicpc.net/problem/8249

 

풀이:

정점을 무한히 일직선으로 폅시다. 이 때, $v$라는 정점은 지구를 동쪽으로 $r$바퀴 돌았는지의 여부와 함께 $(v, r)$이라는 정점으로 바뀝니다. 좀 더 엄밀히 말해서 경도 $0$인 기준선을 서->동 방향으로 몇 번 지났는지라고 생각합시다.

$w_b - w_a$의 부호가 $k$와 같으면 경도 $0$ 기준선을 지나지 않습니다. 즉 $(a, r) \leftrightarrow (b, r)$ 간선이 됩니다. 만약 다르면 기준선을 지납니다. 즉, $a \leftrightarrow b$ 간선은 $(a, r) \leftrightarrow (b, r+k)$ 간선이 됩니다.

이제 $(1, 0)$ 에서 $(1, r)$ $(r \ne 0)$ 으로 가는 최단거리를 구하면 됩니다. 여기서 Dijkstra를 돌리면 $O(NM \log M)$ 정도의 시간에 문제를 풀 수 있습니다.

 

이제 Dijkstra를 돌리는데, $(1, 0)$에서 $(1, r)$ $(r \ne 0)$인 아무 정점으로 가는 최단거리를 생각해봅시다. 이 최단거리는 같은 정점을 $3$번 지나지 않습니다.

증명: 만약 같은 정점을 $3$번 지난다고 생각합시다. $(v, r_1), (v, r_2), (v, r_3)$ 순으로 차례대로 지난다고 하고, $(v, r_3) \rightarrow (1, r_3 + d)$ 로 $d$바퀴를 더 돌아서 도착한다고 합시다. $r_1 + d, r_2 + d$ 중 하나는 $0$이 아닙니다. 즉, $r_3$에서 $d$바퀴를 돌 필요가 없이 $r_1$ 혹은 $r_2$에서 $d$바퀴를 미리 더 돌면 되기 때문에 모순입니다.

 

즉, 같은 $v$에 대해서는 $3$개 이상의 $r$에 대한 정보를 저장할 필요가 없습니다.

Dijkstra 에서 $v$ 에 대한 길이를 저장하는 배열에 $r$에 대한 길이를 최대 $2$번만 저장하면 $O(M \log M)$ 시간에 문제를 해결할 수 있습니다.

 

코드: https://www.acmicpc.net/source/share/cb2d8afc05d54f47a549251566d682cd