Submission #1565687

---

Source Code Expand

from sys import stdin
input = stdin.readline
def BFS(K,edges,N):
  dist=[-1]*N
  stack=[]
  stack.append(K)
  dist[K]=0
  while stack:
    label=stack.pop(-1)
    for i,c in edges[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        stack+=[i]
  return dist
 
N=int(input())
edges=[ [] for i in range(N)]
for i in range(N-1):
  a,b,c=map(int,input().split())
  edges[a-1]+=[(b-1,c)]
  edges[b-1]+=[(a-1,c)]
Q,K=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(Q)]
distance=BFS(K-1,edges,N)
for i in range(Q):
  print(distance[xy[i][0]-1]+distance[xy[i][1]-1])

Submission Info

Judge Result