1916

날짜 : 2023. 03. 13

사용 언어 : python

 

문제

 

 

코드

import sys
import heapq

n = int(sys.stdin.readline())  # 도시의 개수
m = int(sys.stdin.readline())  # 버스의 개수
graph = [[] for _ in range(n + 1)]  # 전체 그래프 (0은 생략)
dist = [int(1e9)] * (n + 1)  # 기준 노드에서 각 노드까지 길이(start 기준)

for _ in range(m):
    s, e, c = map(int, sys.stdin.readline().split())  # 시작, 도착, 비용
    graph[s].append([e, c])  # s -> e까지의 비용 c 추가
#for i in graph: print(i)


def dijkstra(start):
    q = list()
    heapq.heappush(q, (0, start))  # 거리, 노드번호
    dist[start] = 0

    while q:
        d, now = heapq.heappop(q)  # start 에서 now 까지의 거리
        #print("%d에서 %d까지 확인"%(start, now))
        if dist[now] < d : continue  # 최신화 필요 없는 경우
        for node in graph[now]:  # now 노드 연결 노드 탐색 [노드번호, cost]
            cost = d + node[1]  # 거쳐서 가는 경우
            if cost < dist[node[0]]:  # 인접노드간 최단거리 최신화
                dist[node[0]] = cost
                heapq.heappush(q, (cost, node[0]))
        #print(q)
    return


s, e = map(int, sys.stdin.readline().rstrip().split())  # 시작, 도착지점 입력
dijkstra(s)

print(dist[e])

 

 

풀이

- 다익스트라를 활용하여 풀이하는 문제였다.

 

 

알게된 점

- 

 

 

참고 사이트

- https://techblog-history-younghunjo1.tistory.com/248

[Python] 우선순위 큐를 활용한 개선된 다익스트라(Dijkstra) 알고리즘