시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 32 MB | 242 | 73 | 54 | 28.571% |
승현이는 정점의 개수가 N개인 방향성 그래프 G와 음이 아닌 정수들로 구성된 배열 A[1],A[2],⋯,A[N−1]을 가지고 있습니다. 정점들에는 0 이상 N−1 이하의 정수 번호가 붙어 있으며, 각 간선에는 가중치가 존재합니다. 초기에 이 방향성 그래프에는 간선이 하나도 없었기 때문에, 승현이는 허전함을 느꼈습니다. 이에 그는 아래와 같은 방식으로 간선들을 잇기로 했습니다.
승현이는 이렇게 간선을 추가한 뒤에 임의의 정점에서 출발하여 다른 정점에 도착하는 최단 경로의 길이를 구하고자 합니다.
첫 번째 줄에 그래프 G의 정점의 수 N (5≤N≤2,000)이 주어집니다. 두 번째 줄에 A[1],A[2],⋯,A[N−1] (0≤A[1],A[2],⋯,A[N−1]≤10,000)이 공백을 사이로 두고 주어집니다. 세 번째 줄에 질의의 수 Q (1≤Q≤200,000)가 주어집니다. 이후 Q개 줄이 주어지는데, 이 중 i번째 줄 (1≤i≤Q)에는 두 개의 정수 ai와 bi (0≤ai,bi<N, ai≠bi)가 공백을 사이로 두고 주어집니다.
여러분은 각 질의마다 ai번 정점에서 출발하여 bi번 정점에 도착하는 최단 경로의 길이를 한 줄에 하나씩 입력에서 주어진 순서대로 출력해야 합니다. 단 이러한 최단 경로가 존재하지 않을 경우 −1을 출력합니다.
5 3 2 0 0 4 1 0 2 1 3 0 0 1
3 3 5 4
6 0 3 0 0 0 4 0 4 1 2 2 3 4 0
3 -1 -1 6