#5250 최단 경로들

Here is a random problem for you!

lml 2023. 10. 10. 11:24

도로가 닫혔을 때 최단 경로의 길이를 구하여라...

특이사항

1. N = 2000이라는 점. 예상 복잡도는 O(N^2lgN)이나 O(NM)...?

2. 제거되는 경로는 최단경로인 '운 좋은 경로'에 속하는 것.

단상 1.

운 좋은 경로에 있는 모든 도시를 운 좋은 도시라고 부르자.

운 좋은 경로에 있는 모든 도로를 제거한 상태에서, 운 좋은 도시로부터의 거리를 안다고 가정해보자.

점 y의 v[x]로부터의 거리를 dist[x][y]라고 하자.

distL[i][y] = min(dist[1][y] + dist[1][v[1]], dist[2][y] + dist[1][v[2]],.... ,dist[i][y] + dist[1][v[i]]) 라고 하자.

distR[i][y] = min(dist[k][y] + dist[k][v[k]], dist[k - 1][y] + dist[k][v[k - 1]], ..., + dist[i][y] + dist[k][v[i]]) 라고 하자.

-> 그러면 dist를 이미 안다면, 각 점에 대해 O(N)으로, 총 O(N^2)으로 모든 distL, distR의 값을 알 수 있다.

-> v[i], v[i + 1] 사이의 간선이 삭제된 그래프에서는 min(distL[i] + distR[i + 1])이 답이 될 것이다.

-> 사실 dist를 몰라도 distL, distR은 순서대로 구할 수 있다.

-> 전부 제거한 채로 다익을 굴리면 distL[1], v[1] - v[2] 간선을 넣으면 distL[2], ... 순서대로 간선 추가하며 알 수 있음

그러면 이제 dist만 어떻게 구하면 된다.

일반적으로 이걸 구하는 것은 불가능하다. 플로이드 워셜을 쓰면 O(N^3), 다익을 쓰면 O(VElgV) 정도가 될 것

그래서 2의 특이사항을 쓰면 가능할 것 같다는 생각을 하였다.

혹시나 개멋지게도, 내가 모르는 이유가 있어서 다익을 K번 순서대로 쓰면 VElgV보다 절약되나 했는데 아님

좀 생각을 해보다가 정보가 갱신되는 양상을 고민하게 되었다.

DFS-tree를 정의하듯이 대충 v[1]을 root로 하는 Dijk-tree를 상상해보자.

이제 이 상황에서 v[1] - v[2] 간선을 추가하면 무슨일이 벌어지는지 관찰해보자.

1. v[2]는 반드시 Dijk-tree 상에서 v[1]과 이웃한 점이 된다.

2. 어떤 점 i의 dist가 바뀌면 (즉, distL[1][i] != distL[2][i]) i의 subtree에 있는 모든 점의 dist[2][j] 값이 변화한다.

-> 이때 반드시 (distL[2][ancestor]의 변화량) <= (distL[2][child]) 를 만족한다.

-> 심지어는 새롭게 생겨난 Dijk-tree에서는 parent-child 관계가 뒤바뀔 수도 있다.

// 중단, dijk tree에서 dist를 그냥 안 구하고 푸는 방향으로 전환

단상 2

또 든 생각은 처음에 그냥 그래프 그대로 Dijk-tree를 만들었을 때 어떻게 되느냐이다.

Dijk tree를 만들고 lucky path를 제거하면 root가 lucky 도시들인 forest 느낌으로 생기게 된다. 이들은 Lead라 부르자.

그러면! lucky path를 쓰지 않고 start부터 end까지 가려면 tree 사이의 간선을 사용하면 된다는 사실을 알 수 있다.

-> start부터 시작하여 dijk-tree를 만들고 각 점들이 {거리 = dist1, 내 tree의 root = lead1}가 최소가 되도록 설정한다.

-> end부터 시작하여 dijk-tree를 만들고 각 점들이 {거리 = dist2, -(내 tree의 root) = -lead2}가 최소가 되도록 설정한다

그러면 서로 다른 두 점 (u, v) 사이에 거리 w인 간선이 있다고 가정하자

그러면 lead1[u] 부터 lead2[v] - 1까지의 답은 dist1[u] + dist2[v] + w 이하가 되어야 한다

-> 따라서 모든 간선에 대해서 (u, v, w)가 lucky path가 아닌 경우 [lead1[u], lead2[v])를 갱신해주면 된다. (Lazy seg)

-> O(MlgK + MlgN)

단상 3.

풀이를 보니 세그를 안쓰는 방법이 있다.

Dijk tree를 만들어 놓고 (O(MlgN)), K번 마다 선을 끊어버리고 DFS로 최단경로 갱신 및 답 구하기. (O(MN))