백준 / 노드사이의 거리 / 1240번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 노드사이의 거리 / 1240번 (골드 5단계)

문제 사이트: https://www.acmicpc.net/problem/1240

 

문제 설명

 

---

 

나의 풀이

 

from collections import deque

INF = 1e8

def dijkstra(start, end):
    visited = [INF] * (N + 1)
    q = deque([(start, 0)])  # 이 부분을 수정합니다

    while q:
        current, distance = q.popleft()

        if (visited[current] < distance):
            continue

        for i in range(len(graph[current])):
            next, weight = graph[current][i]
            nextDistance = weight + distance
            if next == end:
                return nextDistance
            if (nextDistance < visited[next]):
                visited[next] = nextDistance
                q.append((next, nextDistance))

    return visited[end]  # 끝까지 못 찾은 경우, INF 반환 또는 종료


# 입력 처리
N, M = map(int, input().split())

result = []
graph = { i : [] for i in range(1, N + 1)}

for _ in range(N - 1):
    x, y, dis = map(int, input().split())
    graph[x].append((y, dis))
    graph[y].append((x, dis))

for _ in range(M):
    a, b = map(int, input().split())
    result.append(int(dijkstra(a, b)))

for i in result:
    print(i)

---

※ 알아야 할 것

 

다익스트라 알고리즘을 알고 있으면 쉽게 풀 수 있는 문제다!

https://newkimjiwon.tistory.com/85

다익스트라 알고리즘(Dijkstra)