1854번: K번째 최단경로 찾기 첫째 줄에 n, m, k가 주어진다. (1 ≤ n ≤ 1000, 0 ≤ m ≤ 2000000, 1 ≤ k ≤ 100) n과 m은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다. 이어지는 m개의 줄에 www.acmicpc.net 분석 최단 경로를 표현하는 리스트를 k개의 row를 갖는 2차원 리스트의 형태로 변경 기존 다익스트라 로직에서, k번째 노드를 찾기 위해서는 노드를 여러번 사용하기 때문에 visited 로직 삭제 다익스트라 로직 수정 코드 1. 최단 거리 리스트를 1차원이 아닌 k개의 row를 갖는 2차원 리스트로 선언 distance = array = [[INF] * k for _ in range(n+1)] q = [(..

다익스트라 음수간선 X S 시작점부터 다른 모든 노드로 가는 최단거리 구하는 알고리즘 기출 : 음수간선이 없는데 시작점이 있고 최단거리 구하는 문제 원리 최단거리를 구할 노드에서 시작하여 거리가 입력된 노드 중 최단거리가 가장 작은 노드를 돌아가며 선택 노드를 돌아가면서, 더 거리가 나오면 값 갱신하여 저장 우선순위 큐 파이썬 우선순위 큐, 힙 우선순위 큐(Priority Queue) 큐(Queue)는 먼저 들어오는 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조 우선순위 큐는 먼저 들어오는 데이터가 아니라, 우선순위가 높은 데이터가 먼저 나 karla.tistory.com 풀이 (PriorityQueue) import sys from queue import Priori..