| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 4 초 | 1024 MB | 86 | 44 | 20 | 39.216% |
세훈이와 찬우는 수많은 그래프 문제를 풀며 좋은 그래프 문제에 대한 소신을 가지게 되었다.
세훈이와 찬우는 1ドル$반적이면서 차수가 3ドル$ 이상인 정점이 3ドル$개 미만인 그래프에 1 && 3 그래프라는 이름을 붙였다. 그래프를 정의하였으니 정점 사이의 최단 거리를 찾는 것은 여러분의 몫이다. 정점이 $V$개, 간선이 $E$개인 1 && 3 그래프가 주어질 때, 임의의 두 정점 사이의 최단 거리를 계산하는 쿼리를 $Q$번 처리하는 프로그램을 작성해 보자.
첫째 줄에 정점의 개수 $V,ドル 간선의 개수 $E,ドル 쿼리의 수 $Q$가 공백으로 구분되어 주어진다. $(2 \le V \le 500,000円;$ $V-1 \le E \le 500,000円;$ 1ドル \le Q \le 200,000円)$
둘째 줄부터 $E$개의 줄에 걸쳐 각 간선이 잇는 두 정점의 번호 $x,ドル $y$와 간선의 가중치 $c$가 공백으로 구분되어 주어진다. $(1 \le x,y \le V;$ 1ドル \le c \le 10^9;$ $x \neq y)$
그 다음 줄부터 $Q$개의 줄에 걸쳐 $a,ドル $b$가 공백으로 구분되어 주어진다. 이는 $a$번 정점과 $b$번 정점 사이의 최단 거리를 계산하는 쿼리를 의미한다. $(1 \le a, b \le V)$
입력으로 주어지는 모든 수는 정수이며, 주어지는 그래프는 1 && 3 그래프이다.
$Q$개의 줄에 걸쳐 쿼리의 결과를 입력받은 순서대로 한 줄에 하나씩 출력한다.
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