| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 4 초 | 1024 MB | 94 | 46 | 30 | 40.000% |
정점이 $N$개이고 간선이 $M$개인 단순 무향 가중 연결 그래프가 주어진다.
두 정점 $s$, $e$의 최단 거리를 구하는 쿼리를 $Q$번 처리하시오.
첫 번째 줄에 정점의 개수 $N$과 간선의 개수 $M$이 공백으로 구분되어 주어진다. $(1 \le N \le 10^{5};$ $N-1 \le M \le N+50)$
두 번째 줄부터 $M$개의 줄에 걸쳐 각 줄에 간선이 잇는 두 정점 $u$, $v$와 간선의 가중치 $w$가 공백으로 구분되어 주어진다. $(1 \le u, v \le N;$ $u \neq v;$ $1 \le w \le 10^{9})$
$M+2$번째 줄에 쿼리의 개수 $Q$가 주어진다. $(1 \le Q \le 10^{5})$
$M+3$번째 줄부터 $Q$개의 줄에 걸쳐 각 줄에 최단 거리를 구해야 하는 두 정점 $s$, $e$가 공백으로 구분되어 주어진다. $(1 \le s, e \le N)$
첫 번째 줄부터 $Q$개의 줄에 걸쳐 각 줄에 정점 $s$에서 정점 $e$까지의 최단 거리를 출력한다.
4 3 1 2 3 4 1 1 3 1 2 2 1 3 4 2
2 4
6 8 1 2 1 3 1 2 2 3 2 5 2 1 3 5 4 5 4 5 2 6 3 4 2 3 4 1 6 4 1 5 5 6 3
4 4 0 5
School > 한국디지털미디어고등학교 > 제4회 디미고 프로그래밍 챌린지 M번