다익스트라 알고리즘(Dijkstra's Algorithm) - 구름LEVEL
다익스트라 알고리즘(Dijkstra's Algorithm)
Quiz Info
Quiz Info
다익스트라 알고리즘(Dijkstra's Algorithm)
100points
Participant
48
Solved Rate
79.1%
4
4

다익스트라 알고리즘(Dijkstra's Algorithm)은 가중치가 있는 그래프에서 노드 사이의 최단 경로를 찾는 알고리즘 입니다.

동작 과정을 살펴보면 다음과 같습니다.

1. 아직 확인되지 않은 거리는 초기값을 무한으로 설정하여 둔다.

2. 이웃 노드를 방문하여 거리를 계산하며 그래프를 업데이트 시킨다.

3. 더 빠른 경로를 발견하면 값을 새로 업데이트한다.

그래프와 출발점을 입력하고 각 노드들까지의 최단거리를 출력하는 프로그램(다익스트라 알고리즘)을 작성하십시오.

* 이 문제에서 간선은 모두 양방향 간선입니다.


입력

첫 줄에 정점(N)과 간선(E)의 수를 순서대로 입력

다음 줄 부터 E 줄 동안 간선의 정보를 시작노드, 도착노드, 가중치 순으로 입력

마지막 줄에 시작점 입력

출력

N: V 꼴로 시작점에서 각 정점까지의 최소거리를 표현(입출력 예시 참고)



Input/Output Example
:
Blank
:
Line Break
:
Tab
Example 1
Input
34
125
134
232
231
1
Output
1:0
2:5
3:4
Example 2
Input
44
123
132
215
343
2
Output
1:3
2:0
3:5
4:8
⋇ Please keep the input and output formats carefully
Quiz Info
Q & A
Q&A forum that anyone can ask and answer.
Share your questions and answers with other students and grow together!

Registered Questions(0)