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

www.acmicpc.net/problem/1240

1240번: 노드사이의 거리

# import sys
# input = sys.stdin.readline

from collections import deque
N, M = map(int, input().split())
link_arr = [list() for _ in range(N + 1)]
for _ in range(N - 1):
    n1, n2, w = map(int, input().split())
    link_arr[n1].append((n2, w))
    link_arr[n2].append((n1, w))

for _ in range(M):
    s, e = map(int, input().split())
    def bfs(start, end):
        q = deque()
        q.append(start)
        visit = [-1] * (N + 1)
        visit[start] = 0
        while q:
            cur = q.popleft()
            if cur == end: break
            for adj_node, adj_dist in link_arr[cur]:
                if visit[adj_node] > -1: continue
                visit[adj_node] = visit[cur] + adj_dist
                q.append(adj_node)
        return visit[end]
    print(bfs(s, e))

가중치가 주어져있어서 다익스트라인줄 알았으나 BFS로 충분히 풀수 있었다. 다익스트라로도 충분히 풀 수 있을거같긴하다

bfs를 살짝 응용해서 최소 거리를 구하는 문제인데 visit에 저장하는 값을 노드사이의 거리(가중치)를 더해서 구하면 된다.

 

얘도 easy