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
from collections import deque
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

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

    dist = [-1 for i in range(N)]
    Q, K = map(int, readline().split())
    dist[K-1] = 0
    q = deque([[K - 1, 0, -1]])
    while q:
        v, d, parent = q.popleft()
        dist[v] = d
        for child in G[v]:
            if child[0] == parent:
                continue
            q.append([child[0], d + child[1], v])

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n = ni()
    edge = [[] for _ in range(n)]
    for _ in range(n - 1):
        a, b, c = ns()
        a -= 1
        b -= 1
        edge[a].append((b, c))
        edge[b].append((a, c))

    dist_table = [-1 for _ in range(n)]

    def dfs(node, dist):
        for t, cost in edge[node]:
            if dist_table[t] == -1:
                dist_table[t] = dist + cost
                dfs(t, dist_table[t])
        return

    q, k = ns()
    k -= 1
    dist_table[k] = 0
    dfs(k, 0)

    for _ in range(q):
        x, y = ns()
        print(dist_table[x - 1] + dist_table[y - 1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())

graph = [[] for i in range(n)]

for i in range(n-1):
    a, b, c = map(int, input().split())

    graph[a-1].append((b-1, c))
    graph[b-1].append((a-1, c))

q_num, k = map(int, input().split())

seen = [-1 for i in range(n)]
seen[k-1] = 0


q = deque()

q.append((k-1, 0))

while len(q) > 0:
    cur = q.popleft()

    cur_node = cur[0]
    cur_cost = cur[1]

    for nx in graph[cur_node]:
        nx_node = nx[0]
        nx_cost = cur_cost + nx[1]

        if seen[nx_node] < 0:
            seen[nx_node] = nx_cost
            q.append((nx_node, nx_cost))

queries = []

for i in range(q_num):
    queries.append(list(map(int, input().split())))


for query in queries:
    print(seen[query[0]-1] + seen[query[1]-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
n = int(input())
visited = [0]*n
dist = [0]*n
edge = [[] for _ in range(n)]
def dfs(k):
    visited[k]=1
    for i in edge[k]:
        if visited[i[0]]==0:
            dist[i[0]]=i[1]+dist[k]
            dfs(i[0])


    return dist
def main():

    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())
    #頂点kから各頂点への距離を最初に求めておくdist[i]:頂点kから頂点iまでの距離　 dist[k]=0

    visited[k-1]=1
    dist = dfs(k-1)

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


    for i in range(q):
        print(res[i])
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
n = int(input())
visited = [0]*n
def dfs(edge, dist, k):
    visited[k]=1
    for i in edge[k]:
        if visited[i[0]]==0:
            dist[i[0]]=i[1]+dist[k]
            dfs(edge, dist, i[0])


    return dist
def main():
    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())
    #頂点kから各頂点への距離を最初に求めておくdist[i]:頂点kから頂点iまでの距離　 dist[k]=0
    dist = [0]*n
    visited[k-1]=1
    dist = dfs(edge, dist, k-1)

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


    for i in range(q):
        print(res[i])
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#dpでできないかな？
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
tree=[[] for i in range(n)]
for i in range(n-1):
    a,b,c=MI()
    a-=1
    b-=1
    tree[a].append([b,c])
    tree[b].append([a,c])
q,k=MI()
#print(tree)
k-=1
dis=[[-1,0] for i in range(n)]
dis[k][0]=0
def dfs(x):
    for s,t in tree[x]:
        if dis[s][0]>=0:
            continue
        dis[s][0]=dis[x][0]+t
        if x==k:
            dis[s][1]=s
        else:
            dis[s][1]=x
        dfs(s)
dfs(k)
for i in range(q):
    x,y=MI()
    x-=1
    y-=1
    print(dis[x][0]+dis[y][0])

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
edge = []
dist = [-1]*(n+1)
for i in range(n+1):
    edge.append([])
for i in range(n-1):
    a,b,c = map(int,input().split())
    edge[a].append((b,c))
    edge[b].append((a,c))
q,k = map(int,input().split())
dist[k] = 0
que = deque([k])
used = set()
used.add(k)
while que:
    here = que.popleft()
    dist_here = dist[here]
    for i in edge[here]:
        if i[0] not in used:
            que.append(i[0])
            used.add(i[0])
            dist[i[0]] = dist_here + i[1]
for i in range(q):
    x,y = map(int,input().split())
    print(dist[x]+dist[y])

Submission status: Accepted

Solution code:
import heapq
N = int(input())
edges = [[] for _ in range(N)]
for i in range(N-1):
    a, b, c = map(int, input().split())
    edges[a-1].append([b-1, c])
    edges[b-1].append([a-1, c])
Q, K = map(int, input().split())
K -= 1


ans_list = []
def dijkstra(edges, num_v, start):
    dist = [float('inf')] * num_v
    dist[start] = 0
    q = []
    heapq.heappush(q, [0, start])

    while len(q) > 0:
        _, u = heapq.heappop(q)
        for edge in edges[u]:
            if dist[edge[0]] > dist[u] + edge[1]:
                dist[edge[0]] = dist[u] + edge[1]
                heapq.heappush(q, [dist[u] + edge[1], edge[0]])
    return dist
base = dijkstra(edges,  N, K)
for i in range(Q):
    x, y = map(lambda n: int(n) - 1, input().split())
    x_K = base[x]
    K_y = base[y]
    ans_list.append(x_K + K_y)

for i in ans_list:
    print(i)

Submission status: Accepted

Solution code:
from collections import defaultdict
 
n = int(input())
V = defaultdict(list)

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

def dfs(source):
    dist = [-1]*(n+1)
    dist[source] = 0
    q = [source]
    while q:
        a = q.pop()
        for b in V[a]:
            if dist[b[0]]!=-1:
                continue
            dist[b[0]] = dist[a] + b[1]
            q.append(b[0])
    return dist

q,k = map(int, input().split())
dk = dfs(k)

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

Submission status: Accepted

Solution code:
# Kから各頂点への距離をメモする
# xからKの距離とyからKの距離を足したものが答え

import sys
readline = sys.stdin.readline

N = int(readline())
G = [[] for i in range(N)]
for i in range(N - 1):
  a,b,c = map(int,readline().split())
  G[a-1].append((b-1,c))
  G[b-1].append((a-1,c))

dist = [-1 for i in range(N)] # Kからの距離
Q,K = map(int,readline().split())

dist[K - 1] = 0
from collections import deque
# 頂点、Kからの距離, 親
q = deque([[K - 1, 0, -1]])
while q:
  v, d, parent = q.popleft()
  dist[v] = d
  for child in G[v]:
    if child[0] == parent:
      continue
    q.append([child[0],d + child[1], v])

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

Submission status: Accepted

Solution code:
from heapq import heappop,heappush
def dijkstra(s,n,edge):
  """
  始点sから各頂点への最短距離を返す

  Parameters
  ----------
  s : int
      視点とする頂点（0-indexed）
  n : int
      グラフの要素数
  eage:list
      グラグ

  Returns
  -------
  dist ：list
  始点sから各頂点への最短距離
  """
  dist=[float("inf")]*n
  dist[s]=0
  used=[-1]*n
  hq=[[dist[s],s]]
  while hq:
    d,cur=heappop(hq)
    if dist[cur]<d:continue # 距離が最小でない場合は飛ばす
    for nx,nxd in edge[cur]:
      if dist[cur]+nxd<dist[nx]:
        dist[nx]=dist[cur]+nxd
        used[nx]=cur
        heappush(hq,[dist[cur]+nxd,nx])
  return dist

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


q,k=map(int,input().split())
xy=[list(map(int,input().split()))for _ in range(q)]
d=dijkstra(k-1,n,edge)
for x,y in xy:
  print(d[x-1]+d[y-1])

Submission status: Accepted

Solution code:

from collections import deque
N=int(input())
T=[[] for _ in range(N)]
for i in range(N-1):
    a,b,c=map(int, input().split())
    T[a-1].append((b-1,c))
    T[b-1].append((a-1,c))

Q,K=map(int, input().split())
que=deque([(K-1,0)])
done=[-1]*N
while que:
    t=que.popleft()
    now,nowd=t
    done[now]=nowd
    for nex in T[now]:
        nexnode,nexd=nex
        if done[nexnode]!=-1:
            continue
        else:
            que.append((nexnode, nowd+nexd))

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

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
G = [[] for _ in range(N)]
for i in range(N-1):
  a, b, c = map(int, input().split())
  G[a-1].append((b-1, c))
  G[b-1].append((a-1, c))
  
Q, K = map(int, input().split())
K -= 1
costs = [0] * N
stack = deque([K])
visited = [False]*N
visited[K] = True

while stack:
  now = stack.pop()
  for nxt, c in G[now]:
    if visited[nxt]:
      continue
    visited[nxt] = True
    costs[nxt] = costs[now] + c
    stack.append(nxt)
    
for i in range(Q):
  x, y = map(int, input().split())
  print(costs[x-1] + costs[y-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(4100000)

N = int(input())
INF = 10 ** 14
edges = [[] for _ in range(N)]
for _ in range(N-1):
    a, b, c = map(int,input().split())
    edges[a-1].append((b-1, c))
    edges[b-1].append((a-1, c))

Q, K = map(int,input().split())
d = [INF] * N
d[K-1] = 0

def dfs(x):
    for u, cost in edges[x]:
        if d[u] == INF:
            d[u] = d[x] + cost
            dfs(u)

dfs(K-1)

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

Submission status: Accepted

Solution code:
from collections import deque
INFTY = 10**14+100
N = int(input())
T = {i:[] for i in range(1,N+1)}
for _ in range(N-1):
    a,b,c = map(int,input().split())
    T[a].append((b,c))
    T[b].append((a,c))
Q,K = map(int,input().split())
dist = [INFTY for _ in range(N+1)]
hist = [0 for _ in range(N+1)]
dist[K] = 0
hist[K] = 1
heap = deque([(K,0)])
while heap:
    x,d = heap.popleft()
    for y,d1 in T[x]:
        if hist[y]==0:
            heap.append((y,d+d1))
            dist[y] = d+d1
            hist[y]=1
for _ in range(Q):
    x,y = map(int,input().split())
    print(dist[x]+dist[y])

Submission status: Accepted

Solution code:
n = int(input())
import sys
sys.setrecursionlimit(10**8)
def D(now,pre,SUM):
    dist[now] = SUM
    for BC in G[now]:
        if BC[0] == pre:
            continue
        D(BC[0],now,SUM+BC[1])



G = [[] for _ in range(n)]
for i 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から頂点kまでの最短経路を求めておいて、kからyまでの最短経路を求めておく
k -= 1
# ここで作っとく?
dist = [0] * n
D(k,-1,0)
for i in range(q):
    x,y = map(lambda m:int(m)-1, input().split())
    print(dist[x] + dist[y])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

n = int(input())
edge = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b, c = [int(x) for x in input().split()]
    edge[a - 1].append([c, b - 1])
    edge[b - 1].append([c, a - 1])
q, k = [int(x) for x in input().split()]
# print(edge)
import heapq
def dijkstra(s):
    d = [float("inf")]*n
    used = [False]*n
    d[s] = 0
    used[s] = True
    queue = []
    for e in edge[s]:
        heapq.heappush(queue, e)
    while queue:
        # print(queue, d)
        cost, to = heapq.heappop(queue)
        if used[to]:
            continue
        d[to] = cost
        used[to] = True
        for e in edge[to]:
            # print(e)
            if used[e[1]]:
                continue
            heapq.heappush(queue, [d[to] + e[0], e[1]])
    return d

d = dijkstra(k - 1)
# print(d)
ans = []
for _ in range(q):
    x, y = [int(x) for x in input().split()]
    ans.append(d[x - 1] + d[y - 1])
for i in ans:
    print(i)

Submission status: Accepted

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

def bfs():
    q = deque([K-1])
    dist = [-1]*N
    dist[K-1] = 0
    
    while q:
        v = q.popleft()
        
        for nv, w in G[v]:
            if dist[nv]==-1:
                dist[nv] = dist[v]+w
                q.append(nv)
    
    return dist

N = int(input())
G = [[] for _ in range(N)]

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

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

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

Submission status: Accepted

Solution code:
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)]

graph = [[] for _ in range(N)]
for ai, bi, ci in abc:
    graph[ai - 1].append((bi - 1, ci))
    graph[bi - 1].append((ai - 1, ci))

MY_INF = 10 ** 18
import heapq

q = [(0, K - 1)]
d = [MY_INF] * N
d[K - 1] = 0
while len(q) > 0:
    dist, src = heapq.heappop(q)
    for dst, c_tmp in graph[src]:
        dist_tmp = dist + c_tmp
        if d[dst] > dist_tmp:
            d[dst] = dist_tmp
            heapq.heappush(q, (dist_tmp, dst))

for xi, yi in xy:
    print(d[xi - 1] + d[yi - 1])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

N = int(input())

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

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

d = [-1] * (N + 1)
d[K] = 0
stack = [K]
while stack:
    now = stack.pop()
    for tmp in G[now]:
        next_ = tmp[0]
        if d[next_] == -1:
            d[next_] = d[now] + tmp[1]
            stack.append(next_)

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

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
INF = 10**15
def dijkstra(s, edges):
    n = len(edges)
    que = []
    d = [INF] * n
    prev = [-1] * n
    d[s] = 0
    heappush(que, (0, s))
    while len(que) > 0:
        (c, v) = heappop(que)
        if d[v] < c:
            continue
        for (cc, w) in edges[v]:
            if d[w] > d[v] + cc:
                d[w] = d[v] + cc
                prev[w] = v
                heappush(que, (d[w], w))
    return d, prev

n = int(input())
edges = [[] for i in range(n)]
for i in range(n-1):
    ai, bi, ci = map(int, input().split())
    ai, bi = ai-1, bi-1
    edges[ai].append((ci, bi))
    edges[bi].append((ci, ai))

q, k = map(int, input().split())
k -= 1
d, prev = dijkstra(k, edges)
ans = []
for i in range(q):
    xi, yi = map(int, input().split())
    xi, yi = xi-1, yi-1
    ans.append(d[xi]+d[yi])

for i in ans:
    print(i)

Submission status: Accepted

Solution code:
N = int(input())
edges = [[] for _ in range(N)]

for _ in range(N - 1):
    fr, to, cost = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append((to, cost))
    edges[to].append((fr, cost))

Q, K = map(int, input().split())
K -= 1
XY = [tuple(map(lambda a: int(a) - 1, input().split())) for _ in range(Q)]

minDist = [10**18] * N
minDist[K] = 0
st = [K]
while st:
    now = st.pop()
    dist = minDist[now]
    for to, c in edges[now]:
        d = dist + c
        if minDist[to] > d:
            minDist[to] = d
            st.append(to)

ans = [minDist[x] + minDist[y] for x, y in XY]
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline

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

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

import heapq
INF = 10**18
def dijkstra_heap(s, edge, n):
    d = [INF] * n
    used = [True] * n #True: not used
    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

d = dijkstra_heap(k, edge, n)
for i in range(q):
    x, y = map(int, input().split())
    x, y = x-1, y-1
    print(d[x]+d[y])

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())
    Ans = [0] * Q
    Dist = [-1] * N
    q = deque()
    q.append((K-1, K-1, 0))
    while q:
        nowN, pre, dist = q.popleft()
        if Dist[nowN] == -1:
            Dist[nowN] = dist
            for nextN, cost in Edge[nowN]:
                if nextN != pre: q.append((nextN, nowN, dist + cost))
    for i in range(Q):
        x, y = map(int, input().split())
        Ans[i] = Dist[x-1] + Dist[y-1]

    print(*Ans, sep="\n")
    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)

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

def dfs(start):
    for x,cost in graph[start]:
        if d[x]==-1:
            d[x]=d[start]+cost
            dfs(x)

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

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

INF = float('inf')

n = int(input())
dn = {v: [] for v in range(n)}
for _ in range(n - 1):
    a, b, c = map(int, input().split())
    dn[a - 1] += [(b - 1, c)]
    dn[b - 1] += [(a - 1, c)]

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

dd = [INF] * n
queue = []
heappush(queue, (0, k - 1))
while queue:
    d, v = heappop(queue)
    for neighbor, c in dn[v]:
        dtmp = d + c
        if dtmp < dd[neighbor]:
            dd[neighbor] = dtmp
            heappush(queue, (dtmp, neighbor))


for x, y in xy:
    print(dd[x - 1] + dd[y - 1])

Submission status: Accepted

Solution code:
from collections import defaultdict
import heapq


def dijkstra(N, start, adj_nodes, costs):
    INF = 10**15
    dist = [INF for _ in range(N)]
    dist[start] = 0
    frontier = [(0, start)]
    while len(frontier) > 0:
        d, node = heapq.heappop(frontier)
        for next_node in adj_nodes[node]:
            if dist[next_node] > d + costs[(node, next_node)]:
                dist[next_node] = d + costs[(node, next_node)]
                frontier.append((dist[next_node], next_node))
    return dist


def main():
    N = int(input())
    adj_nodes = defaultdict(list)
    costs = defaultdict(int)
    for _ in range(N - 1):
        a, b, c = list(map(int, input().split(' ')))
        a -= 1
        b -= 1
        adj_nodes[a].append(b)
        adj_nodes[b].append(a)
        costs[(a, b)] = c
        costs[(b, a)] = c
    Q, K = list(map(int, input().split(' ')))
    K -= 1
    queries = [list(map(lambda q: int(q) - 1, input().split(' '))) for _ in range(Q)]
    dist = dijkstra(N, K, adj_nodes, costs)
    for query in queries:
        x, y = query
        print(dist[x] + dist[y])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq
import collections

INF = 10 ** 16

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

class edge:
    def __init__(self, to, cost): self.to, self.cost = to, cost

def main():
    N = Z()
    E = collections.defaultdict(list)
    for _ in range(N-1):
        a, b, c = ZZ()
        E[a].append(edge(b, c))
        E[b].append(edge(a, c))
    Q, K = ZZ()

    def dijkstra(s):
        que = list()
        heapq.heapify(que)
        newd = [INF] * (N+1)
        newd[s] = 0
        heapq.heappush(que, [newd[s], s])

        while que:
            p = heapq.heappop(que)
            v = p[1]
            if newd[v] < p[0]: continue
            for e in E[v]:
                if newd[e.to] > newd[v] + e.cost:
                    newd[e.to] = newd[v] + e.cost
                    heapq.heappush(que, [newd[e.to], e.to])
        return newd

    dist = dijkstra(K)
    output = []

    for _ in range(Q):
        x, y = ZZ()
        output.append(dist[x] + dist[y])
    print(*output, sep='\n')

    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq
def dijkstra_heap(s,node_edges):
    '''
    ノードの入力は0-indexedに修正してから用いる
    returnはノードごとの最小コストを格納したリスト
    '''
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [False] * n #True:未確定
    d[s] = 0
    used[s] = True
    edgelist = []
    # 始点がスタートになってるedgeをヒープキューに追加
    for e in node_edges[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        # ヒープキューからコスト最小のedgeをpop
        minedge = heapq.heappop(edgelist)
        # 該当edgeの行き先が確定済みになってなければこれを通って処理が続く
        if used[minedge[1]]:
            continue
        v = minedge[1]
        # 該当edgeの行き先のコストを更新
        d[v] = minedge[0]
        used[v] = True
        for e in node_edges[v]:
            if not used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

n = int(input())
node_edges = [[] for _ in range(n)]
for i in range(n-1):
    start, end, cost = map(int,input().split())
    start -= 1
    end -= 1
    node_edges[start].append([cost, end])
    node_edges[end].append([cost, start])
num_q, stop = map(int,input().split())
stop -= 1

dist_from_stop = dijkstra_heap(stop, node_edges)
ans_ls = [0] * num_q
for i in range(num_q):
    start, end = map(int,input().split())
    start -= 1
    end -= 1
    ans_ls[i] = dist_from_stop[start] + dist_from_stop[end]
for ans in ans_ls:
    print(ans)

Submission status: Accepted

Solution code:
import heapq
n = int(input())

def dijkstra_heap(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [False] * n #True:未確定
    d[s] = 0
    used[s] = True
    edgelist = []
    # 始点がスタートになってるedgeをヒープキューに追加
    for e in node_edges[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        # ヒープキューからコスト最小のedgeをpop
        minedge = heapq.heappop(edgelist)
        # 該当edgeの行き先が確定済みになってなければこれを通って処理が続く
        if used[minedge[1]]:
            continue
        v = minedge[1]
        # 該当edgeの行き先のコストを更新
        d[v] = minedge[0]
        used[v] = True
        for e in node_edges[v]:
            if not used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

node_edges = [[] for i in range(n)]

for i in range(n-1):
    start, end, cost = map(int,input().split())
    start -= 1
    end -= 1
    node_edges[start].append([cost, end])
    node_edges[end].append([cost, start])

num_q, stop = map(int,input().split())
stop -= 1
d_ls = dijkstra_heap(stop)

ans_ls = [0] * num_q
for i in range(num_q):
    start, end = map(int,input().split())
    start -= 1
    end -= 1
    total_dist = d_ls[start] + d_ls[end]
    ans_ls[i] = total_dist
for ans in ans_ls:
    print(ans)

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())
to = [[] for _ in range(n)]

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

dist = [0 for _ in range(n)]
visited = [False for _ in range(n)]

def dfs(root):
    d = deque()
    d.append(root)
    while len(d) > 0:
        v = d.pop()
        visited[v] = True
        for u, c in to[v]:
            if visited[u]:
                continue
            d.append(u)
            dist[u] = dist[v]+c

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

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