Dijkstra 알고리즘을 이용한 최단경로와 거리를 출력하시오.
입력
n (num. of vertex)
e (num. of undirected edge)
n1 n2 d1 (vertex id, vertex id, distance: id는 0부터 시작)
... (e개 만큼의 edge 정보)
q (질문의 개수)
m1 m2 (src. vertex id, dest vertex id)
m3 m4 (q개 만큼의 질문)
출력
k1 k2 ... kx d (첫번째 질문에 대한 답: 경로(src. to dst.), 거리)
k3 k6 ....ky d
아래와 같은 예시 그래프에 대해서 다음과 같이 동작하여야 한다.
Vertex는 3개 (0, 1, 2 id), edge 개수는 3개, edge weight는 모두 1
0 ---- 1 ---- 2
| |
--------------|
입력의 예
3
3
0 1 1
0 2 1
1 2 1
2
0 2
2 1
출력의 예
0 2 1
2 1 1 (끝에 줄바꿈)