1 && 3 그래프

시간 제한4초메모리 제한1024 MB

요약
차수가 3 이상인 정점이 2개 미만인 특수한 연결 그래프에서 여러 최단거리 질의를 빠르게 처리하는 문제입니다.
난이도

보통10점 중 6점

유형
그래프, 최단 경로, 구현
정답자
아직 제출이 없습니다

문제

세훈이와 찬우는 많은 그래프 문제를 풀면서 좋은 그래프 문제의 조건을 생각하게 되었다.

  • 세훈이는 특별한 예외 처리가 필요하지 않은 일반적인 그래프가 주어져야 한다고 생각한다. 여기서 일반적인 그래프란 중복 간선이 없고, 모든 정점이 연결되어 있으며, 서로 다른 두 정점을 잇는 간선만 있는 무방향 그래프를 말한다.
  • 찬우는 차수가 큰 정점이 많을수록 그래프가 복잡해진다고 생각한다. 구체적으로, 차수가 33 이상인 정점의 개수는 33개 미만이어야 한다.

두 사람은 위 조건을 모두 만족하는 그래프를 1 && 3 그래프라고 부르기로 했다. 정점이 VV개, 간선이 EE개인 1 && 3 그래프가 주어진다. 두 정점 사이의 최단 거리를 묻는 쿼리 QQ개를 처리하는 프로그램을 작성하라.

입력

첫째 줄에 정점의 개수 VV, 간선의 개수 EE, 쿼리의 수 QQ가 공백으로 구분되어 주어진다. (2≤V≤500000;V−1≤E≤500000;1≤Q≤200000)(2 \le V \le 500000; V-1 \le E \le 500000; 1 \le Q \le 200000)

다음 EE개의 줄에는 각 간선이 잇는 두 정점 xx, yy와 간선의 가중치 cc가 공백으로 구분되어 주어진다. (1≤x,y≤V;1≤c≤109;x≠y)(1 \le x,y \le V; 1 \le c \le 10^9; x \ne y)

그 다음 QQ개의 줄에는 두 정점 aa, bb가 공백으로 구분되어 주어진다. 이는 aa번 정점과 bb번 정점 사이의 최단 거리를 묻는 쿼리이다. (1≤a,b≤V)(1 \le a,b \le V)

입력으로 주어지는 모든 수는 정수이며, 주어지는 그래프는 1 && 3 그래프이다.

출력

QQ개의 줄에 걸쳐 각 쿼리의 정답을 입력 순서대로 한 줄에 하나씩 출력한다.

예제1

  1. 예제 1

    입력
    15 18 8
1 2 5
2 3 1
3 4 1
4 1 5
1 5 1
5 6 1
1 7 1
7 8 100
8 9 1
9 10 1
1 10 1
1 15 2
15 10 100
10 14 1
14 13 5
13 12 5
12 11 1
11 10 1
4 12
12 14
2 4
3 6
1 10
7 9
8 9
10 15
    예상 출력
    8
3
2
8
1
3
1
3