-
728x90
### 다익스트라 알고리즘 탬플릿 ###
n, m = map(int, input().split()) k = int(input()) graph = [[] for _ in range(n + 1)] visited = [False] * (n + 1) distance = [99999] * (n + 1) for i in range(n + 1): a, b, c = map(int, input().split()) graph[a].append((b, c)) def getSmallestNode(): minValue = 99999 index = 0 for i in range(1, n + 1): if not visited[i] and distance[i] < minValue: minValue = distance[i] index = i return index def dijkstra(start): distance[start] = 0 visited[start] = 0 for j in graph[start]: distance[j[0]] = j[1] for _ in range(n - 1): now = getSmallestNode() visited[now] = True for k in graph[now]: cost = distance[now] + k[1] if cost < distance[k[0]]: distance[k[0]] = cost dijkstra(k) print(distance) """ 5 6 1 5 1 1 1 2 1 1 3 3 2 3 1 2 4 5 3 4 2 """
후기
네가 코테를 할 때 쓸 탬플릿을 저장해놓으려고 한다.
이 코드는 다익스트라 탬플릿 코드로 쓰고자 합니다.
728x90'백준 코딩 테스트' 카테고리의 다른 글
다익스트라 알고리즘 - 배열에 cost가 주어질 시 탬플릿 코드 (0) 2024.01.28 [백준] 백준 풀 문제 정리 (0) 2023.07.10 백준 2143 - 두배열의 합 (0) 2021.04.19 백준 2632번 - 피자판매 (0) 2021.04.19 백준 7453번 - 합이 0인 네 정수 (0) 2021.04.19