백준 1240 [노드 사이의 거리] 파이썬

https://www.acmicpc.net/problem/1240

# 백준 1240 노드사이의 거리
import sys
from collections import deque
input = sys.stdin.readline

# N: 노드 개수, M: 거리 구해야 하는 쌍의 개수
N, M = map(int, input().split())

# 그래프 인접 리스트 초기화 (1-indexed)
graph = [[] for _ in range(N + 1)]

# 노드 간 거리 저장용 2차원 배열
# 초기에는 -1로 설정 (방문하지 않은 상태를 의미)
costs = [[-1 for _ in range(N + 1)] for _ in range(N + 1)]

# 간선 정보 입력 (양방향 연결)
for _ in range(N - 1):
    A, B, cost = map(int, input().split())
    graph[A].append((B, cost))
    graph[B].append((A, cost))

# 각 노드 i에 대해 BFS를 수행하여 모든 다른 노드와의 거리 계산
for i in range(1, N + 1):
    costs[i][i] = 0  # 자기 자신과의 거리는 0
    q = deque()
    q.append(i)

    while q:
        node = q.popleft()
        for next_node, cost in graph[node]:
            # 아직 방문하지 않은 노드인 경우 거리 누적
            if costs[i][next_node] == -1:
                costs[i][next_node] = costs[i][node] + cost
                q.append(next_node)

# M개의 쿼리 처리: A와 B 노드 사이의 거리 출력
for _ in range(M):
    A, B = map(int, input().split())
    print(costs[A][B])