Festivals In JOI Kingdom (JOI 2012)

koistudy에서 채점할수 있다.

1. Naive (N^3 + QMlgM)

일단 플로이드로 모든 쌍 최단경로를 구하면 축제지로부터의 distance를 알 수가 있다.

그리고, 전체 간선을 축제지로부터의 거리가 큰 순으로 정렬하고, 서로소 집합(union-find tree)를 사용해서 쿼리의 두 정점이 합쳐질때까지 거리 제한을 줄여가면 풀수 있다. 단지 복잡도가 O(N^3 + QMlgM) 이라는 기겁할만한 시간이라 문제지. 플로이드를 다익스트라 * K로 대체할 수 있는데 의미없으니 생략.

2. Dijkstra 한번 쓰기 (QMlgM)

naive algorithm을 들여다 본 결과 모든 쌍 최단경로 알고리즘을 쓰라고 만든 문제가 아니라는 건 자명해졌다. 그런데 엄청 쉽게 한번의 다익스트라로 풀수가 있다.

그냥 K개의 점을 다 dist = 0으로 priority queue에 넣은 다음에 모든 점을 다 찾아버리면 된다.

진짜 이 생각을 왜 못했지;

N^3 -> MlgM이 되어서, 총 시간복잡도는 QMlgM이 된다.

3. 약간의 상향 (MlgM + QN)

역시 약간의 생각을 더하면..

위 방식은 QMlgM으로 쿼리마다 그때 그때 간선을 소트하는데, 처음에 한번 소트해 놓으면 그때그때 간선을 소트할 필요가 없어진다. 고로 일단은 MlgM + QM은 쉽게 얻을 수가 있다.

그런데, 만약에 축제지로부터의 거리가 큰 순으로 만든 Spanning Tree를 생각해보면, 그때 합치는 간선은 항상 Spanning Tree의 부분집합일 것이다. 즉, Spanning Tree에 포함되지 않는 간선은 생각할 필요가 없다. 즉, 쿼리가 주어졌을때 Spanning Tree에서 dfs를 통해서 경로를 찾으면 된다. 이 방법을 사용하면 O(MlgM + QN)에 해결 가능하다.

4. 자료 구조를 통한 상향 (MlgM + QlgN)

트리의 1번 정점을 루트로 잡고 이 방법으로 최적화하면 O(MlgM + QlgN)에 풀 수 있다. parent, minimum을 sparse table로 만들어놓으면 쉽게 풀 수 있다.