[ICPC 본선 대비 뇌셋] Day 22

Day를 그냥 연장시키는 이유는 예뻐보이기 위해서이고 딱히 다른 이유는 없다. 남는 시간동안에 몇문제 더 풀어보기로 했다.

백준 5250번 최단 경로들 www.acmicpc.net/problem/5250

5250번: 최단 경로들

신기한 문제인거같다.

[생각 1] 한 간선이 빠졌을 때 다른 최단 경로를 생각하면 뭔가 이전의 최단경로를 잘 이용해야할 것 같은 느낌이 든다. 따라서, 처음에 주어진 최단경로의 시작을 a, b라고 하면, a와 b로부터 각각 다익스트라를 해준다.

[생각 2] 어떤 간선이 빠졌을 때 최단경로에서 절대 지나지 않는 점 또는 무조건 지나는 점이 무엇일까를 생각하면 다음과 같은 생각을 할 수 있다. 다익스트라를 이용해 a를 루트로 하는 트리를 만들자(pq에 점이 pop될 때 트리에 추가된다.)

[관찰 1]트리의 한 점 c의 자식들 사이의 최단경로는 c의 조상들을 지나지 않는다.

참조그림

간선 $e_{xy}$를 지날 수 없다고 하고 최단경로임을 가정하자.

a의 자손중 y의 자손이 아닌 점 u에서, y의 자손중 한 점 v로 가는 간선이 무조건 하나 이상 존재한다.(b가 y의 자손이기 때문.) 한편, v와 b는 모두 x의 자손이므로, v에서 b로 가는 최단경로는 절대 e를 지나지 않음이 관찰 1에 의해 보장된다. 따라서 다음 식이 성립한다.

[식 1] $최단경로의 길이 = dist(a, u) + w_{uv} + dist(v, b)$

[풀이] 트리의 간선이 아닌 그래프의 모든 간선에 u, v에 대해, line a-b와 겹치는 부분을 c, d라고 하자. c와 d사이의 간선들이 빠졌을 때 가능한 최솟값으로 [식 1]의 값을 업데이트해준다. 레이지 세그를 써주면 된다.

[시간복잡도]: $O(MlgN)$