From: 2018-10-29 00:00:00 To: 2018-12-31 00:00:00 Now: 2024-04-27 11:25:50 Status: Public

D - Dijkstra's Algorithm

Time Limit: 1s Memory Limit: 128MB

Submissions: 2220 Solved: 419

Description

(교재 24.3장)

Dijkstra's algorithm을 구현하여, source node A에서부터 다른 노드 (A포함)로 가는 최소 방문 cost를 모두 출력하는 코드를 작성하시오.

*주의사항

1. Python으로 작성하는 경우, 인풋 첫번째 줄처럼 숫자가 아닌 string을 입력받기 위해서는 raw_input 사용

2. Min-priority queue는 직접 구현하여 사용 (단, DECREASE-KEY operation에 유의)

Input

Line 0: names of vertices, separated by comma ex) A,B,C,D,E,F,G (sorted alphabetically)

Line 1: the number of edges n

Line 2~(n+1): one edge per line, edge = (vertex_from,vertex_to,weight)

Output

Line 0: shortest path distance from A to A

Line 1: shortest path distance from A to B

Line 2: shortest path distance from A to C

...

Sample Input

A,B,C,D,E
10
A,B,10
A,C,5
B,C,2
B,D,1
C,B,3
C,D,9
C,E,2
D,E,4
E,A,7
E,D,6

Sample Output