다익스트라 최단 거리

왜 이 문제를 푸나요?

가중치가 있는 그래프에서는 단순 BFS로 최단 거리를 구할 수 없습니다. 가장 가까운 후보부터 확정하고 간선을 완화하는 다익스트라의 핵심을 익힙니다.

정점 수 n, 방향 간선 [출발, 도착, 가중치] 목록, 시작 정점이 주어집니다. 시작점에서 모든 정점까지의 최단 거리 리스트를 반환하세요. 도달할 수 없는 정점은 -1이며 가중치는 모두 0 이상입니다.

dijkstra(n, edges, start)

인접 리스트와 이진 힙 사용 시 O((V+E) log V)

실행하면 아래 순서대로 채점합니다. print() 출력도 이 순서대로 쌓입니다.

#	이름	`n`	`edges`	`start`	기대값
1	여러 경로	`5`	`[[0, 1, 4], [0, 2, 1], [2, 1, 2], [1, 3, 1], [2, 3, 5]]`	`0`	`[0, 3, 1, 4, -1]`
2	가중치 0	`3`	`[[0, 1, 0], [1, 2, 2], [0, 2, 5]]`	`0`	`[0, 0, 2]`
3	간선 없음	`3`	`[]`	`1`	`[-1, 0, -1]`
4	일부 정점 도달 불가	`4`	`[[0, 1, 3], [1, 2, 4]]`	`0`	`[0, 3, 7, -1]`
5	나중에 더 짧은 경로 발견	`4`	`[[0, 1, 10], [0, 2, 2], [2, 1, 3], [1, 3, 1], [2, 3, 9]]`	`0`	`[0, 5, 2, 6]`

Python 표준 라이브러리는 사용할 수 있습니다. 함수 이름과 매개변수는 제시된 형태를 유지하세요.