시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 45 | 16 | 14 | 45.161% |
영민이의 멘토링 조는 항상 킹십리역 $G$번 출구에서 만나기로 약속 장소를 정한다. 하지만 킹십리역은 구조가 매우 복잡하기 때문에 $G$번 출구를 찾아가기란 쉽지 않다.
킹십리역은 각각의 출구를 정점으로 하고, 두 출구 사이의 통로 구간을 간선으로 하는 하나의 그래프로 나타낼 수 있다. 서로 다른 두 출구는 최대 1개의 통로 구간으로 연결되며, 임의의 두 출구 사이에 이동 가능한 경로가 반드시 존재한다. 영민이는 특정 출구에서 매번 $G$번 출구를 찾아가면서 킹십리역 내부 구조를 학습한다.
특정 출구에서 $G$번 출구로 찾아가는 경로는 여러 통로 구간으로 구성될 수 있다. 그런데 영민이는 특정 경로를 한 번 이용하면 그 경로에 너무 익숙해진 나머지, 해당 경로를 구성하지 않는 모든 통로 구간의 헷갈리는 정도가 일정량 증가한다. 처음에 모든 통로 구간의 헷갈리는 정도는 $0$이며, 각 구간을 이동하는 데 걸리는 시간은 해당 구간의 길이와 헷갈리는 정도의 합과 같다.
영민이가 $G$번 출구를 찾아갈 때는 다음과 같은 규칙을 순서대로 따른다.
출구들의 정보가 주어질 때, 다음과 같은 질의를 수행하는 프로그램을 작성하시오.
첫 번째 줄에 출구의 개수 $N$과 두 출구 사이를 연결하는 통로 구간의 개수 $M$, $G$가 공백으로 구분되어 주어진다. $(2 \le N \le 100\,000,\ N-1 \le M \le \min(10^6, \frac{N(N-1)}{2}), \ 1 \le G \le N)$
두 번째 줄부터 $M$개의 줄에 각 통로의 양 끝 출구의 번호 $a, b$와 통로 구간의 길이 $d$가 주어진다. 모든 통로 구간의 길이는 정수이다. $(1 \le a, b \le N,\ a ≠ b, 1 \le d \le 10\,000)$
$M+2$ 번째 줄에 질의의 개수 $Q$가 주어진다. $(1 \le Q \le 100\,000)$
$M+3$ 번째 줄부터 $Q$개의 줄에 문제에서 설명한 형태의 질의가 한 줄에 하나씩 주어진다. $(1 \le i \le N,$ $i \ne G,$ $1 \le v \le 10\,000)$
1번 질의에서 $v$의 값은 항상 정수이고, 2번 질의는 1개 이상 주어진다.
2번 질의에 대해 한 줄에 하나씩 $i$번 출구에서 $G$번 출구까지 이동한다고 가정할 때 걸리는 시간을 출력한다.
5 6 3 1 3 10 1 4 25 4 5 14 3 5 30 2 3 8 3 4 24 6 1 4 2 2 5 1 5 4 1 2 3 1 2 2 2 1
32 21
5 7 3 2 1 8 5 4 1 3 2 10 1 3 4 4 3 1 2 4 5 3 5 10 4 2 1 1 1 2 2 5 2 2
4 6 10
University > 한양대학교 > 제8회 한양대학교 프로그래밍 경시대회 > Advanced Division C번