Problem:


Score : 400 points

Problem Statement

You are given a tree with N vertices.

Here, a tree is a kind of graph, and more specifically, a connected undirected graph with N-1 edges, where N is the number of its vertices.

The i-th edge (1≤i≤N-1) connects Vertices a_i and b_i, and has a length of c_i.

You are also given Q queries and an integer K. In the j-th query (1≤j≤Q):

find the length of the shortest path from Vertex x_j and Vertex y_j via Vertex K.

Constraints

3≤N≤10^5 

1≤a_i,b_i≤N (1≤i≤N-1) 

1≤c_i≤10^9 (1≤i≤N-1) 

The given graph is a tree.

1≤Q≤10^5 

1≤K≤N 

1≤x_j,y_j≤N (1≤j≤Q) 

x_j≠y_j (1≤j≤Q) 

x_j≠K,y_j≠K (1≤j≤Q) 

Input

Input is given from Standard Input in the following format:  

N  
a_1 b_1 c_1  
:  
a_{N-1} b_{N-1} c_{N-1}
Q K
x_1 y_1
:  
x_{Q} y_{Q}

Output

Print the responses to the queries in Q lines.

In the j-th line j(1≤j≤Q), print the response to the j-th query.

Sample Input 1

5
1 2 1
1 3 1
2 4 1
3 5 1
3 1
2 4
2 3
4 5

Sample Output 1

3
2
4

The shortest paths for the three queries are as follows:

Query 1: Vertex 2 → Vertex 1 → Vertex 2 → Vertex 4 : Length 1+1+1=3 

Query 2: Vertex 2 → Vertex 1 → Vertex 3 : Length 1+1=2 

Query 3: Vertex 4 → Vertex 2 → Vertex 1 → Vertex 3 → Vertex 5 : Length 1+1+1+1=4 

Sample Input 2

7
1 2 1
1 3 3
1 4 5
1 5 7
1 6 9
1 7 11
3 2
1 3
4 5
6 7

Sample Output 2

5
14
22

The path for each query must pass Vertex K=2.

Sample Input 3

10
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000
6 7 1000000000
7 8 1000000000
8 9 1000000000
9 10 1000000000
1 1
9 10

Sample Output 3

17000000000



Sample input:
5
1 2 1
1 3 1
2 4 1
3 5 1
3 1
2 4
2 3
4 5


Sample output:
3
2
4

Submission status: Accepted

Solution code:
import sys
import heapq

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7
depth = [[] for _ in range(10 ** 5)]

def resolve():
    n = int(input())

    edge = [[] for _ in range(n)]
    for _ in range(n - 1):
        a, b, c = map(int, input().split())
        edge[a - 1].append([c, b - 1])
        edge[b - 1].append([c, a - 1])

    q, k = map(int, input().split())
    Query = [list(map(int, input().split())) for _ in range(q)]

    def dfs(v, p, d):
        depth[v] = d
        for c, u in edge[v]:
            if u == p:
                continue
            dfs(u, v, d + c)

    # 各頂点からkまでの最短距離を計算
    dfs(k - 1, -1, 0)

    # xからk,kからyの最短距離を足す
    for x, y in Query:
        res = depth[x - 1] + depth[y - 1]
        print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys
import heapq

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())

    edge = [[] for _ in range(n)]
    for _ in range(n - 1):
        a, b, c = map(int, input().split())
        edge[a - 1].append([c, b - 1])
        edge[b - 1].append([c, a - 1])

    q, k = map(int, input().split())
    Query = [list(map(int, input().split())) for _ in range(q)]

    def dijkstra_heap(s):
        # 始点sから各頂点への最短距離
        d = [float("inf")] * n
        used = [True] * n  # True:未確定
        d[s] = 0
        used[s] = False
        edgelist = []
        for e in edge[s]:
            heapq.heappush(edgelist, e)
        while len(edgelist):
            minedge = heapq.heappop(edgelist)
            # まだ使われてない頂点の中から最小の距離のものを探す
            if not used[minedge[1]]:
                continue
            v = minedge[1]
            d[v] = minedge[0]
            used[v] = False
            for e in edge[v]:
                if used[e[1]]:
                    heapq.heappush(edgelist, [e[0] + d[v], e[1]])
        return d

    dist = dijkstra_heap(k - 1)

    for x, y in Query:
        res = dist[x - 1] + dist[y - 1]
        print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import math
import fractions
#import sys
#input = sys.stdin.readline

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ZipArray(a):
    aa = [[a[i],i]for i in range(n)]

    aa.sort(key = lambda x : x[0])
    for i in range(n):
        aa[i][0]=i+1
    aa.sort(key = lambda x : x[1])
    b=[aa[i][0] for i in range(len(a))]
    return b

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def Zeros(a,b):
    if(b<=-1):
        return [0 for i in range(a)]
    else:
        return [[0 for i in range(b)] for i in range(a)]

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''

def rln(s):
    return range(len(s))

#a = list(map(int, input().split()))

#################################################
#################################################
#################################################
#################################################

class NB:
    v=0
    d=0

n = int(input())
nb = [[] for i in range(n)]
for i in range(n-1):
    a,b,c = list(map(int, input().split()))
    nbi = NB()
    nbi.v = b-1
    nbi.d = c
    nb[a-1].append(nbi)
    nbi = NB()
    nbi.v = a-1
    nbi.d = c
    nb[b-1].append(nbi)

q,k = list(map(int, input().split()))

queue = [k-1]
done = 0
dist = [0 for i in range(n)]

while(len(queue)>done):
    now = queue[done]
    for i in nb[now]:
        if(dist[i.v]==0 and i.v!=k-1):
            dist[i.v] = dist[now]+i.d
            queue.append(i.v)
    done+=1
#print(dist)

for i in range(q):
    a,b=list(map(int, input().split()))
    print(dist[a-1]+dist[b-1])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n = int(input())

dis = [ 0 for _ in range(n)]  # 距離
adj = [[] for _ in range(n)] # 隣接リスト

for _ in range(n-1):
    a, b, c = map(int, input().split())
    a -= 1;b-= 1
    adj[a].append([b, c])
    adj[b].append([a, c])

# v; 現在の頂点
# p; vの親
# d; 現在の距離
def dfs(v, p, d):
    dis[v] = d
    for i, c in adj[v]:
        if i == p:
            continue
        dfs(i, v, d+c)

q, k = map(int, input().split())
k -= 1

dfs(k, -1, 0)

for _ in range(q):
    x, y = map(int, input().split())
    x -= 1;y -= 1
    print(dis[x] + dis[y])

Submission status: Accepted

Solution code:
# !入力
# グラフの構築
# クエリの入力
# Kからの各点のの距離をdfs
# クエリの処理
from collections import deque
n=int(input())
edge=[[]for _ in range(n)]
for i in range(n-1):
  a,b,c=map(int,input().split())
  edge[a-1].append((b-1,c))
  edge[b-1].append((a-1,c))
q,k=map(int,input().split())
dist=[0]*n
seen=[False]*n
todo=deque([k-1])
while todo:
  par=todo.popleft()
  seen[par]=True
  for cld,cost in edge[par]:
    if dist[cld]==0:
      if seen[cld]==False:
        dist[cld]=dist[par]+cost
        seen[cld]=True
        todo.append(cld)

for i in range(q):
  x,y=map(int,input().split())
  print(dist[x-1]+dist[y-1])

Submission status: Accepted

Solution code:
# !入力
# グラフの構築
# クエリの入力
# Kからの各点のの距離をdfs
# クエリの処理
from collections import deque
n=int(input())
edge=[[]for _ in range(n)]
for i in range(n-1):
  a,b,c=map(int,input().split())
  edge[a-1].append((b-1,c))
  edge[b-1].append((a-1,c))
q,k=map(int,input().split())
dist=[0]*n
seen=[False]*n
todo=deque([k-1])
while todo:
  par=todo.pop()
  seen[par]=True
  for cld,cost in edge[par]:
    if dist[cld]==0:
      if seen[cld]==False:
        dist[cld]=dist[par]+cost
        seen[cld]=True
        todo.append(cld)

for i in range(q):
  x,y=map(int,input().split())
  print(dist[x-1]+dist[y-1])

Submission status: Accepted

Solution code:
import heapq
inf=float("inf")


def dijkstra(k):
    color=["white" for _ in range(n+1)]
    D=[inf for _ in range(n+1)]
    M=[[] for _ in range(n+1)]

    for a,b,c in ABC:
        M[a].append([c,b])
        M[b].append([c,a])

    D[k]=0
    color[k]="gray"
    queue=[[0,k]]
    heapq.heapify(queue)

    while len(queue)>0:
        u=heapq.heappop(queue)[1]
        color[u]="black"

        for i,j in M[u]:
            if color[j]!="black":
                if D[u]+i<D[j]:
                    D[j]=D[u]+i
                    color[j]="gray"
                    queue.append([D[j],j])

    return D


n=int(input())
ABC=[list(map(int,input().split())) for _ in range(n-1)]
q,k=map(int,input().split())
XY=[list(map(int,input().split())) for _ in range(q)]
D=dijkstra(k)

for x,y in XY:
    print(D[x]+D[y])

Submission status: Accepted

Solution code:
from collections import deque

def main():
    n = int(input())
    adjacent = [[] for _ in range(n)]
    for _ in range(n - 1):
        a, b, c = map(int, input().split())
        adjacent[a - 1].append((b - 1, c))
        adjacent[b - 1].append((a - 1, c))
    q, k = map(int, input().split())
    next_search = deque([k - 1])
    searched = set()
    dist = [10**20] * n
    dist[k - 1] = 0
    while next_search:
        p = next_search.popleft()
        if p in searched:
            continue
        searched.add(p)
        for pp, d in adjacent[p]:
            dist[pp] = min(dist[p] + d, dist[pp])
            next_search.append(pp)
    for _ in range(q):
        x, y = map(int, input().split())
        print(dist[x - 1] + dist[y - 1])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin
import sys
input = stdin.readline
sys.setrecursionlimit(10**6)
mod = 10**9+7
 
n = int(input())
m = n-1
graph = [[] for j in range(n)]
d = {}

for i in range(m):
    a,b,c = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
    d[(a-1,b-1)] = d[(b-1,a-1)] = c

q,k = map(int,input().split())
    
# 頂点kから各頂点への距離
dis = [0]*n
    
# v = 現在の頂点
# per = vの親(vが根のときは-1)
# ans = 総距離
def DFS(v,per,ans):
	if not per == -1 :
		dis[v] = ans
	for i in graph[v]:
        # 移動先iがvの親ならスキップ（訪問済みのチェックと同じ）
		if i == per :
			continue
		DFS(i,v,ans+d[(v,i)])

DFS(k-1,-1,0)

for i in range(q) :
  x,y = map(int,input().split())
  print(dis[x-1]+dis[y-1])

Submission status: Accepted

Solution code:
import heapq
 
"""
https://juppy.hatenablog.com/entry/2019/02/18/%E8%9F%BB%E6%9C%AC_python_%E3%83%97%E3%83%A9%E3%82%A4%E3%82%AA%E3%83%AA%E3%83%86%E3%82%A3%E3%82%AD%E3%83%A5%E3%83%BC%28heapq%29%E3%82%92%E7%94%A8%E3%81%84%E3%81%9F%E3%83%97%E3%83%AA%E3%83%A0%E6%B3%95
"""
 
def dijkstra_heap(s,edge):
    #始点sから各頂点への最短距離
    d = [10**10]*n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d
 
################################
N = int(input())
n = N
w = N
 
edge = tuple([] for i in range(n))
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(w-1):
    a,b,c = map(int,input().split())
    edge[a-1].append([c,b-1])
    edge[b-1].append([c,a-1])
 
 
Q,K = map(int,input().split())
dist = dijkstra_heap(K-1,edge)
 
for i in range(Q):
    x,y = map(int,input().split())
    print(int(dist[x-1]+dist[y-1]))

Submission status: Accepted

Solution code:
#jiriki-kibishi-katta
from collections import deque
n = int(input())
p = [[] for _ in range(n+1)]
for _ in range(n-1):
    a, b, c = map(int, input().split())
    p[a].append((b, c))
    p[b].append((a, c))
q, k = map(int, input().split())
visited = [-1]*(n+1)
visited[k] = 0
queue = deque()
queue.append(k)
while len(queue):
    pos = queue.popleft()
    for nxt, w in p[pos]:
        if visited[nxt] != -1:
            continue
        visited[nxt] = visited[pos]+w
        queue.append(nxt)
for i in range(q):
    x, y = map(int, input().split())
    print(visited[x]+visited[y])

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
tree = [[]*(n+1) for _ in range(n+1)]
for i in range(n-1):
    a,b,c = map(int,input().split())
    tree[a].append((b,c))
    tree[b].append((a,c))
q,k = map(int,input().split())
parent = [-1]*(n+1)
distance = [-1]*(n+1)
distance[k] = 0
d = deque()
d.append(k)
while d:
    x = d.popleft()
    for child,length in tree[x]:
        if parent[x] == child:
            continue
        parent[child] = x
        distance[child] = distance[x] + length
        d.append(child)
for i in range(q):
    x,y = map(int,input().split())
    print(distance[x]+distance[y])

Submission status: Accepted

Solution code:
N = int(input())
INF = float('inf')
edges = [[] for i in range(N+1)]
for i in range(N-1):
    a,b,c = list(map(int,input().split()))
    edges[a].append((b,c))
    edges[b].append((a,c))

Q,K = list(map(int,input().split()))
checked = [0]*(N+1)
checked[K] = 1
stack = [K]
distances_from_K = [-1]*(N+1)
distances_from_K[K] = 0
while stack:
    s = stack.pop()
    for t in edges[s]:
        if not checked[t[0]]:
            checked[t[0]] = 1
            distances_from_K[t[0]] = distances_from_K[s] + t[1]
            stack.append(t[0])

for i in range(Q):
    x,y = list(map(int,input().split()))
    print(distances_from_K[x]+distances_from_K[y])

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(1000000)

N = int(input())
Nodes = [{} for i in range(N)]


def search(index, dist):
    neighbors = Nodes[index]
    for key in neighbors:
        if distances[key] is not None:
            continue

        distances[key] = dist + neighbors[key]
        search(key, distances[key])


# 木を作る
for _ in range(N-1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    Nodes[a][b] = c
    Nodes[b][a] = c

# 頂点Kから各点への距離を求める
Q, K = map(int, input().split())
distances = [None for i in range(N)]
distances[K-1] = 0
search(index=K-1, dist=0)

#print(distances)

# 解答
for _ in range(Q):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    print(distances[x] + distances[y])

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
e = [[] for i in range(n)]
for i in range(n-1):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    e[a].append((b,c))
    e[b].append((a,c))

Q,k = map(int,input().split())
k -= 1
d = [-1]*n
d[k] = 0
q =deque([])
q.append(k)
while q:
    now = q.popleft()

    for nex,dis in e[now]:
        if d[nex] == -1:
            d[nex] = d[now]+dis
            q.append(nex)

for i in range(Q):
    x,y = map(int,input().split())
    print(d[x-1]+d[y-1])

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def dfs(G, v, p, dist):
    """G: graph, v: vertex, p: parent"""
    # Loop for each child
    for c, d in G[v]:
        # Avoid multiple access to parent
        if c == p:
            continue
        dist[c] = dist[v] + d
        dfs(G, c, v, dist)


def main():
    N = int(input())
    G = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        G[a].append((b, c))
        G[b].append((a, c))

    Q, K = map(int, input().split())
    x = [0] * Q
    y = [0] * Q
    for i in range(Q):
        x[i], y[i] = map(int, input().split())

    dist = [0] * N
    dfs(G, K-1, -1, dist)
    for i in range(Q):
        ans = dist[x[i]-1] + dist[y[i]-1]
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
from sys import stdin
input=stdin.readline

N=int(input())
a=[0]*(N-1)
b=[0]*(N-1)
c=[0]*(N-1)
L=[ [] for _ in range(N)]
for i in range(N-1):
  a[i],b[i],c[i]= map(int,input().split())
  L[a[i]-1].append((b[i]-1,c[i]))
  L[b[i]-1].append((a[i]-1,c[i]))
Q,K= map(int,input().split())
         
#Lの中のitemの0は接続先、1は距離

d=[ -1 for i in range(N)]

def BFS(x):
  v=deque([x])
  d[x]=0
  
  while len(v)>0:
    s=v.popleft() #sはint
    for item in L[s]:
      if d[item[0]]==-1:
        d[item[0]]=d[s]+item[1]
        v.append(item[0])
BFS(K-1)

x=[0]*Q
y=[0]*Q
for i in range(Q):
  x[i],y[i] = map(int,input().split())
  print(d[x[i]-1]+d[y[i]-1])

Submission status: Accepted

Solution code:
from collections import deque

N=int(input())
a=[0]*(N-1)
b=[0]*(N-1)
c=[0]*(N-1)
L=[ [] for _ in range(N)]
for i in range(N-1):
  a[i],b[i],c[i]= map(int,input().split())
  L[a[i]-1].append((b[i]-1,c[i]))
  L[b[i]-1].append((a[i]-1,c[i]))
Q,K= map(int,input().split())
         
#Lの中のitemの0は接続先、1は距離

d=[ -1 for i in range(N)]

def BFS(x):
  v=deque([x])
  d[x]=0
  
  while len(v)>0:
    s=v.popleft() #sはint
    for item in L[s]:
      if d[item[0]]==-1:
        d[item[0]]=d[s]+item[1]
        v.append(item[0])
BFS(K-1)

x=[0]*Q
y=[0]*Q
for i in range(Q):
  x[i],y[i] = map(int,input().split())
  print(d[x[i]-1]+d[y[i]-1])

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
G = dict([(i,[]) for i in range(1,N+1)])
for i in range(N-1):
  a,b,c = map(int,input().split())
  G[a].append([c,b])
  G[b].append([c,a])
Q,K = map(int,input().split())
q = []
for i in range(Q):
  q.append(list(map(int,input().split())))

d = [0 for i in range(N+1)]
deq = deque([K])
seen = [False for i in range(N+1)]
while len(deq) > 0:
  v = deq.popleft()
  for i in G[v]:
    if seen[i[1]] == False:
      d[i[1]] = d[v] + i[0]
      deq.append(i[1])
      seen[i[1]] = True

for i in range(Q):
  [x,y] = q[i]
  print(d[x]+d[y])

Submission status: Accepted

Solution code:
#BFS
from collections import deque
def bfs(G):
    q=deque()
    q.append((k - 1, -1, 0))

    while q:
        #qの先頭を取り出す
        V, P, C = q.popleft()
        for new, cost in G[V]:
            if new == P:continue
            temp = C + cost
            q.append((new, V, temp))
            stand[new] = temp

n = int(input())
route_list = [[] for i in range(n)]  # 辺の移動の際のコスト
for i in range(n - 1):
    s, t, d = map(int, input().split())
    route_list[s - 1].append((t - 1, d))
    route_list[t - 1].append((s - 1, d))
# print(route_list)
q, k = map(int,input().split())


stand = [0] * n
bfs(route_list)
for i in range(q):
    x, y = map(int,input().split())
    temp = stand[x - 1] + stand[y - 1]
    print(temp)

Submission status: Accepted

Solution code:
N=int(input())

import heapq
def dijkstra_heap(s):
  #始点sから各頂点への最短距離
  #indexが1～Nの場合はNの代わりにN+1
  size_v=N+1
  dist=[float("inf")]*size_v
  used=[False]*size_v
  dist[s]=0
  used[s]=True

  hq_edge=[]
  for v,w in edge[s]:
    heapq.heappush(hq_edge,(w,v))

  while len(hq_edge):
    min_w,min_v=heapq.heappop(hq_edge)
    #まだ使われてない頂点の中から最小の距離のものを探す
    if used[min_v]:
      continue

    dist[min_v]=min_w
    used[min_v]=True
    for v,w in edge[min_v]:
      if not used[v]:
        heapq.heappush(hq_edge,(min_w+w,v))

  return dist

edge=[[] for _ in range(N+1)]
for _ in range(N-1):
  a,b,c=map(int,input().split())
  edge[a].append((b,c))
  edge[b].append((a,c))
#print(edge)

Q,K=map(int,input().split())

dist=dijkstra_heap(K)
#print(dist)

for _ in range(Q):
  x,y=map(int,input().split())
  print(dist[x]+dist[y])

Submission status: Accepted

Solution code:
n=int(input())
G=[[] for i in range(n)]
for i in range(n-1):
  u,v,w=map(int,input().split())
  G[u-1].append([v-1,w])
  G[v-1].append([u-1,w])
dist=[-1]*n
from collections import deque
Q,k=map(int,input().split())
q=deque()
q.append(k-1)
dist[k-1]=0
while q:
  cur=q.popleft()
  for nx,nd in G[cur]:
    if dist[nx]!=-1:continue
    dist[nx]=dist[cur]+nd
    q.append(nx)
for i in range(Q):
  x,y=map(int,input().split())
  x-=1
  y-=1
  print(dist[x]+dist[y])

Submission status: Accepted

Solution code:
import sys
from collections import deque

readline = sys.stdin.readline
N = int(readline())
E = [[] for _ in range(N)]
for _ in range(N-1):
    a, b, c = map(int, readline().split())
    E[a-1].append((b-1, c))
    E[b-1].append((a-1, c))

Q, K = map(int, readline().split())
dist = [-1] * N
dist[K-1] = 0
q = deque([K-1])
while q:
    x = q.pop()
    d = dist[x]
    for i, j in E[x]:
        if dist[i] == -1:
            dist[i] = d + j
            q.append(i)
for _ in range(Q):
    x, y = map(int, readline().split())
    print(dist[x-1] + dist[y-1])

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
N = int(readline())
E = [[] for _ in range(N)]
for _ in range(N-1):
    a, b, c = map(int, readline().split())
    E[a-1].append((b-1, c))
    E[b-1].append((a-1, c))

Q, K = map(int, readline().split())
dist = [-1] * N
dist[K-1] = 0
q = [K-1]
while q:
    x = q.pop()
    d = dist[x]
    for i, j in E[x]:
        if dist[i] == -1:
            dist[i] = d + j
            q.append(i)
for _ in range(Q):
    x, y = map(int, readline().split())
    print(dist[x-1] + dist[y-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500000)

import sys
def input():
    return sys.stdin.readline()[:-1]

N = int(input())

tree = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b, c = map(int, input().split())
    tree[a].append((b, c))
    tree[b].append((a, c))

Q, K = map(int, input().split())

def dfs(start, dist, dists, f=None):
    for n, d in tree[start]:
        if n == f:
            continue
        dists[n] = dist + d
        dfs(n, dist+d, dists, start)

xy = [list(map(int, input().split())) for i in range(Q)]

dists = [0] * (N+1)
dfs(K, 0, dists)

for i in range(Q):
    x, y = xy[i]
    print(dists[x] + dists[y])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500000)

N = int(input())

tree = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b, c = map(int, input().split())
    tree[a].append((b, c))
    tree[b].append((a, c))

Q, K = map(int, input().split())

def dfs(start, dist, dists, f=None):
    for n, d in tree[start]:
        if n == f:
            continue
        dists[n] = dist + d
        dfs(n, dist+d, dists, start)

xy = [list(map(int, input().split())) for i in range(Q)]

dists = [0] * (N+1)
dfs(K, 0, dists)

for i in range(Q):
    x, y = xy[i]
    print(dists[x] + dists[y])

Submission status: Accepted

Solution code:
import heapq
class Graph:
    def __init__(self,v,edgelist,w_v = None,directed = False):
        super().__init__()
        self.v = v
        self.w_e = [{} for _ in [0]*self.v]
        self.neighbor = [[] for _ in [0]*self.v]
        self.w_v = w_v
        self.directed = directed

        for i,j,w in edgelist:
            self.w_e[i][j] = w
            self.neighbor[i].append(j)

    def dijkstra(self,v_n):
        d = [float('inf')]*self.v
        d[v_n] = 0
        prev = [-1]*self.v

        queue = []
        for i,d_i in enumerate(d): heapq.heappush(queue,(d_i,i))
        
        while len(queue)>0:
            d_u,u = queue.pop()
            if d[u]<d_u :continue
            for v in self.neighbor[u]:
                alt = d[u]+self.w_e[u][v]
                if d[v]>alt:
                    d[v] = alt
                    prev[v] = u
                    heapq.heappush(queue,(alt,v))

        return d,prev

    def warshallFloyd(self):
        d = [[10**18]*self.v for _ in [0]*self.v]
        for i in range(self.v):
            d[i][i] = 0
            
        for i in range(self.v):
            for j in self.neighbor[i]:
                d[i][j] = self.w_e[i][j]
            
        for i in range(self.v):
            for j in self.neighbor[i]:
                d[i][j] = self.w_e[i][j]
        
        for k in range(self.v):
            for i in range(self.v):
                for j in range(self.v):
                    check = d[i][k] + d[k][j]
                    if d[i][j] > check:
                        d[i][j] = check
        return d

    def prim(self):
        gb = GraphBuilder(self.v,self.directed)

        queue = []
        for i,w in self.w_e[0].items(): heapq.heappush(queue,(w,0,i))
        rest = [True]*self.v
        rest[0] = False

        v = 1
        while len(queue)>0:
            w,i,j = heapq.heappop(queue)
            if rest[j]:
                gb.addEdge(i,j,w)
                rest[j] = False
                for k,w in self.w_e[j].items():
                    if rest[k]:heapq.heappush(queue,(w,j,k))

        return gb


class Tree():
    def __init__(self,v,e):
        pass

class GraphBuilder():
    def __init__(self,v,directed = False):
        self.v = v
        self.directed = directed
        self.edge = []

    def addEdge(self,i,j,w=1):
        if not self.directed:
            self.edge.append((j,i,w))
        self.edge.append((i,j,w))

    def addEdges(self,edgelist,weight = True):
        if weight:
            if self.directed:
                for i,j,w in edgelist:
                    self.edge.append((i,j,w))
            else:
                for i,j,w in edgelist:
                    self.edge.append((i,j,w))
                    self.edge.append((j,i,w))
        else:
            if self.directed:
                for i,j,w in edgelist:
                    self.edge.append((i,j,1))
            else:
                for i,j,w in edgelist:
                    self.edge.append((i,j,1))
                    self.edge.append((j,i,1))
            

    def addAdjMat(self, mat):
        for i,mat_i in enumerate(mat):
            for j,w in enumerate(mat_i):
                self.edge.append((i,j,w))

    def buildTree(self):
        pass

    def buildGraph(self):
        return Graph(self.v,self.edge,directed=self.directed)
   
def main():
    n = int(input())
    edge = []
    for _ in range(n-1):
        a,b,w = tuple([int(t)for t in input().split()])
        edge.append((a-1,b-1,w))
    gb = GraphBuilder(n)
    gb.addEdges(edge)
    g = gb.buildGraph()
    
    q,k = tuple([int(t)for t in input().split()])
    dijk = g.dijkstra(k-1)[0]
    ans = []
    for _ in range(q):
        x,y = tuple([int(t)-1 for t in input().split()])
        ans.append(dijk[x]+dijk[y])
    for a_i in ans:
        print(a_i)
        
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq

"""
https://juppy.hatenablog.com/entry/2019/02/18/%E8%9F%BB%E6%9C%AC_python_%E3%83%97%E3%83%A9%E3%82%A4%E3%82%AA%E3%83%AA%E3%83%86%E3%82%A3%E3%82%AD%E3%83%A5%E3%83%BC%28heapq%29%E3%82%92%E7%94%A8%E3%81%84%E3%81%9F%E3%83%97%E3%83%AA%E3%83%A0%E6%B3%95
"""

def dijkstra_heap(s,edge):
    #始点sから各頂点への最短距離
    d = [10**10]*n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d
 
################################
N = int(input())
n = N
w = N
 
edge = tuple([] for i in range(n))
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(w-1):
    a,b,c = map(int,input().split())
    edge[a-1].append([c,b-1])
    edge[b-1].append([c,a-1])


Q,K = map(int,input().split())
dist = dijkstra_heap(K-1,edge)
 
for i in range(Q):
    x,y = map(int,input().split())
    print(int(dist[x-1]+dist[y-1]))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    # https://atcoder.jp/contests/abc070/tasks/abc070_d
    # https://atcoder.jp/contests/abc070/submissions/12486326

    import sys
    from collections import deque

    def dijkstra(V, adj, root):
        que = deque()
        que.append(root)
        seen = [-1] * (N + 1)
        seen[root] = 0
        par = [0] * (N + 1)
        child = [[] for _ in range(N + 1)]
        seq = []
        while que:
            v = que.popleft()
            seq.append(v)
            for u, c in adj[v]:
                if seen[u] == -1:
                    seen[u] = seen[v] + c
                    par[u] = v
                    child[v].append(u)
                    que.append(u)
        seq.reverse()

        return seen

    N = int(input())
    V, E = N, N - 1  # 頂点の数、辺の数

    adj = [[] for _ in range(N + 1)]

    for _ in range(N - 1):
        a, b, c = map(int, input().split())  # 頂点aからbにコストc
        adj[a].append((b, c))
        adj[b].append((a, c))
    Q, root = map(int, input().split())  # rootはスタート地点

    d = dijkstra(V, adj, root)
    for _ in range(Q):
        x, y = map(int, input().split())
        print(d[x] + d[y])


resolve()

Submission status: Accepted

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    from collections import deque
    input = sys.stdin.buffer.readline

    N = int(input())
    adj = [[] for _ in range(N+1)]
    for _ in range(N-1):
        a, b, c = map(int, input().split())
        adj[a].append((b, c))
        adj[b].append((a, c))
    Q, root = map(int, input().split())

    que = deque()
    que.append(root)
    seen = [-1] * (N+1)
    seen[root] = 0
    par = [0] * (N+1)
    child = [[] for _ in range(N+1)]
    seq = []
    while que:
        v = que.popleft()
        seq.append(v)
        for u, c in adj[v]:
            if seen[u] == -1:
                seen[u] = seen[v] + c
                par[u] = v
                child[v].append(u)
                que.append(u)
    seq.reverse()

    for _ in range(Q):
        x, y = map(int, input().split())
        print(seen[x] + seen[y])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    N = int(input())
    Edge = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b, c = map(int, input().split())
        Edge[a-1].append((b-1, c))
        Edge[b-1].append((a-1, c))
    Q, K = map(int, input().split())
    q = deque()
    Dist = [-1] * N
    q.append((K-1, K-1, 0))
    while q:
        nowN, preN, nD = q.popleft()
        if Dist[nowN] == -1:
            Dist[nowN] = nD
            for e, add in Edge[nowN]:
                if e != preN: q.append((e, nowN, nD + add))
    Ans = [None] * Q
    for i in range(Q):
        x, y = map(int, input().split())
        Ans[i] = str(Dist[x-1] + Dist[y-1])
    print("\n".join(Ans))

    return 0

if __name__ == "__main__":
    solve()