[백준] 1240번 (파이썬)

난이도 : GOLD V

문제링크 : https://www.acmicpc.net/problem/1240

문제해결 아이디어

• 각 번호의 노드가 이어진 노드 번호와 간선 길이를 같이 저장함
• 문제의 조건의 노드 번호가 나타날때 까지 bfs 순회를 하면서 노드값을 누적해서 더해간다.

import sys
from collections import deque

input = sys.stdin.readline

n,m = map(int, input().split())

graph = [[] for _ in range(n+1)]

for _ in range(n-1):
    i,j,k = map(int,input().split())
    graph[i].append((j,k))
    graph[j].append((i,k))

for _ in range(m):
    s,e = map(int,input().split())
    q = deque()
    q.append((s,0))

    visited = [False] * (n+1)
    visited[s] = True

    while q:
        x,dist = q.popleft()

        if x == e:
            print(dist)
            break
        for num,val in graph[x]:
            if not visited[num]:
                visited[num] = True
                q.append((num, dist+val))