노드사이의 거리

노드사이의 거리

문제

N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라.

입력

첫째 줄에 노드의 개수 N이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리(10,000 이하의 정수)를 입력받는다. 그 다음 줄에는 거리를 알고 싶은 M개의 노드 쌍이 한 줄에 한 쌍씩 입력된다.

출력

M개의 줄에 차례대로 입력받은 두 노드 사이의 거리를 출력한다.

접근방법

노드간 양방향 이동이 가능했기때문에 2차원 배열에 이동거리를 저장해놓았다.

그리고 갈 수 있는 노드에 대하여 방문하지 않았으면 큐에 추가하는 BFS로 구현하였다.

근데 python3 으로 돌리면 에러가 나오고, pyyp3으로 돌리면 정답처리가 된다.

이유를 아직 잘 모르겠지만 찾으면 글을 수정하도록 하겠다.

코드

# 1240 / 노드사이의 거리
# https://www.acmicpc.net/problem/1240

from collections import deque
import sys
input = sys.stdin.readline

def BFS(a, b):

    q = deque()
    q.append(a)
    v = [0] * (N + 1)
    v[a] = 1

    while q:
        cx = q.popleft()

        if cx == b:
            return v[cx]

        for idx in range(1, N + 1):
            if arr[cx][idx] and not v[idx]:
                v[idx] = v[cx] + arr[cx][idx]
                q.append(idx)

N, M = map(int, input().split())

arr = [[0] * (N + 1) for _ in range(N + 1)]

for _ in range(N - 1):
    a, b, c = map(int, input().rstrip().split())

    arr[a][b] = c
    arr[b][a] = c

node = [list(map(int, input().rstrip().split())) for _ in range(M)]
for f, t in node:
    print(BFS(f, t) - 1)