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

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    
    
    from heapq import heapify, heappop, heappush
    
    N = int(input())
    inf = 10 ** 17
    
    
    def dijkstra_heap(start, edge):
        
        d = [inf] * N
        used = [False] * N
        d[start] = 0
        used[start] = True
        edgelist = []
        
        for a, b in edge[start]:
            heappush(edgelist, a * (10 ** 6) + b)
    
        while len(edgelist):
            
            minedge = heappop(edgelist)
            if used[minedge % (10 ** 6)]:
                continue
            node = minedge % (10 ** 6)
            d[node] = minedge // (10 ** 6)
            used[node] = True
    
            for e in edge[node]:
                if not used[e[1]]:
                    heappush(edgelist, (e[0] + d[node]) * (10 ** 6) + e[1])
        return d
    
    
    
    edge = [[] for i in range(N)]
    
    for _ in range(N - 1):
        x, y, z = map(int, input().split())
        edge[x - 1].append((z, y - 1))
        edge[y - 1].append((z, x - 1))
    
    q, k = map(int, input().split())
    d = dijkstra_heap(k - 1, edge)
    
    for _ in range(q):
        x, y = map(int, input().split())
        print(d[x - 1] + d[y - 1])
    
resolve()

Solution (Python):
import heapq
def dijkstra_heap(s):
    
    d = [float("inf")] * N
    used = [True] * N 
    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

N = int(input())

edge = [[] for i in range(N)]  
for i in range(N-1):
    x,y,z = map(int,input().split())
    edge[x-1].append([z,y-1])
    edge[y-1].append([z,x-1])

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

zk = dijkstra_heap(K-1)


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

Solution (Python):
N = int(input())
tree = [[] for _ in range(N)]

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

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

depth = [0 for _ in range(N)]

def dfs(v, p = -1, d = 0):
    St = []
    St.append([v, p, d])
    
    while St:
        cur = St.pop()
        depth[cur[0]] = cur[2]
        for i, j in tree[cur[0]]:
            if i == cur[1]:
                continue
            St.append([i, cur[0], cur[2] + j])

dfs(K)

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

Solution (Python):

from heapq import heappush, heappop
INF = float("inf")
def dijkstra(N, G, s):
    dist = [INF] * N
    que = [(0, s)]
    dist[s] = 0
    while que:
        c, v = heappop(que)
        if dist[v] < c:
            continue
        for t, cost in G[v]:
            if dist[v] + cost < dist[t]:
                dist[t] = dist[v] + cost
                heappush(que, (dist[t], t))
    return dist

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())

dist = dijkstra(N,edge,K-1)

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

Solution (Python):

from heapq import heappush, heappop
INF = 10**20
def dijkstra(N, G, s):
    dist = [INF] * N
    que = [(0, s)]
    dist[s] = 0
    while que:
        c, v = heappop(que)
        if dist[v] < c:
            continue
        for t, cost in G[v]:
            if dist[v] + cost < dist[t]:
                dist[t] = dist[v] + cost
                heappush(que, (dist[t], t))
    return dist

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())

dist = dijkstra(N,edge,K-1)

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

Solution (Python):
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 i, (ai, bi, ci) in enumerate(abc):
    graph[ai - 1].append((bi - 1, ci))
    graph[bi - 1].append((ai - 1, ci))

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

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

Solution (Python):
import sys
input = sys.stdin.readline

n = int(input())
g = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b, c = [int(x) for x in input().split()]
    g[a - 1].append([c, b - 1])
    g[b - 1].append([c, a - 1])
q, k = [int(x) for x in input().split()]
import heapq
def dijkstra(s):
    
    d = [float('inf')]*n
    d[s] = 0
    
    used = [False]*n
    used[s] = True
    
    que = []
    for e in g[s]:
        heapq.heappush(que, e)
    while que:
        minedge = heapq.heappop(que)
        if used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = True
        for e in g[v]:
            if not used[e[1]]:
                heapq.heappush(que, [e[0] + d[v], e[1]])
    return d
d = dijkstra(k - 1)
for _ in range(q):
    x, y = [int(x) for x in input().split()]
    print(d[x - 1] + d[y - 1])

Solution (Python):
from heapq import heappush, heappop

INF = 10**15

def dijkstra(s, edges):
    n = len(edges)
    que = []
    d = [INF] * 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
                heappush(que, (d[w], w))
    return d

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

q, k = map(int, input().split())
x, y = [], []
for i in range(q):
    xi, yi = map(int, input().split())
    xi, yi = xi-1, yi-1
    x.append(xi)
    y.append(yi)

dist = dijkstra(k-1, edge)

for i in range(q):
    print(dist[x[i]]+dist[y[i]])

Solution (Python):
import heapq
from collections import deque
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

        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

    def bfs(self,vartex = 0):
        todo = [True]*self.v
        queue = deque([vartex])
        while(len(queue)>0):
            v = queue.popleft
            todo[v] = False
            yield v
            for v_i in self.neighbor[v]:
                if todo[v_i]:
                    queue.append(v_i)

    def dfs(self,vartex = 0):
        seen = [False]*self.v
        def recdfs(v):
            seen[vartex] = True
            for next_v in self.neighbor[vartex]:
                if (seen[next_v]):continue
                recdfs(next_v)
    
        
            
class Tree():
    def __init__(self,v,e):
        pass

class GraphBuilder():
    def __init__(self,v,directed = False,edge = None, weights = None):
        self.v = v
        self.directed = directed
        self.edge = []
        self.weights = []
        if edge is not None:
            self.addEdges(edge)
        if weights is not None:
            self.addVartex(weights)

    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 in edgelist:
                    self.edge.append((i,j,1))
            else:
                for i,j in edgelist:
                    self.edge.append((i,j,1))
                    self.edge.append((j,i,1))
    
    def addVartex(self,weights):
        if len(weights) != self.v:
            return
        self.weights.extend(weights)

    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)

n = int(input())
edge = []
for i in range(n-1):
  a,b,c = tuple(map(int,input().split()))
  edge.append((a-1,b-1,c))
gb = GraphBuilder(n)
gb.addEdges(edge)
g = gb.buildGraph()

q,k = tuple(map(int,input().split()))
dijk = g.dijkstra(k-1)[0]
for i in range(q):
  a,b = tuple(map(int,input().split()))
  a,b = a-1,b-1
  print(dijk[a]+dijk[b])

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

Solution (Python):
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))
from heapq import heappop,heappush
def dijkstra(s,n,edge):
  inf=10**20
  ans=[inf]*n
  ans[s]=0
  root=[-1]*n
  h=[[0,s]]
  while h:
    c,v=heappop(h)
    if ans[v]<c:continue
    for u,t in edge[v]:
      if c+t<ans[u]:
        ans[u]=c+t
        root[u]=v
        heappush(h,[c+t,u])
  return ans
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])

Solution (Python):
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

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

ans = []
for _ in range(Q):
    X, Y = map(lambda a: int(a) - 1, input().split())
    ans.append(minDist[X] + minDist[Y])

print(*ans, sep='\n')

Solution (Python):
import copy
n = int(input())
graph = [[] for _ in range(n)]
for i in range(n-1):
    a,b,c = map(int,input().split())
    graph[a-1].append([c,b-1])
    graph[b-1].append([c,a-1])
q,k = map(int,input().split())
wait = [k-1]
d = [0]*n
done = [False]*n
while wait:
    nxt = []
    for i in wait:
        for l in graph[i]:
            if not done[l[1]]:
                done[l[1]] = True
                d[l[1]] = d[i] + l[0]
                nxt.append(l[1])
    wait = copy.copy(nxt)


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

Solution (Python):
from collections import deque

N = int(input())

T = [[] for _ in range(N)]
for _ 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())


table = [0] * N
D = deque([K - 1])
visited = set()
while D:
    v = D.pop()
    visited.add(v)
    for x, d in T[v]:
        if x not in visited:
            table[x] = table[v] + d
            D.append(x)

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

Solution (Python):
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())
    a -= 1
    b -= 1
    Edge[a].append((b, c))
    Edge[b].append((a, c))

Q, K = map(int, input().split())
K -= 1
DP = [-1] * N
DP[K] = 0
A = deque()
A.append((0,K))
while len(A) > 0:
    fatigue, now = A.pop()
    for next, cost in Edge[now]:
        if DP[next] > 0:
            continue
        else:
            DP[next] = fatigue + cost
            A.append((fatigue+cost, next))

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

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()

from collections import defaultdict, deque, Counter
from sys import exit
import heapq
import math
import copy
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)

N = getN()
dist = [[] for i in range(N + 1)]
for i in range(N - 1):
    a, b, c = getNM()
    dist[a].append([b, c])
    dist[b].append([a, c])
ignore = [-1] * (N + 1)


def distance(sta):
    
    pos = deque([sta])

    while len(pos) > 0:
        u = pos.popleft()
        for i in dist[u]:
            if ignore[i[0]] == -1:
                ignore[i[0]] = ignore[u] + i[1]
                pos.append(i[0])

Q, K = getNM()
ignore[K] = 0
distance(K)

ans = []
for i in range(Q):
    x, y = getNM()
    ans.append(ignore[x] + ignore[y])
for i in ans:
    print(i)

Solution (Python):

n=int(input())
graph={i:{} for i in range(1,n+1)}
for i in range(n-1):
    a,b,d=map(int,input().split())
    graph[a][b]=d
    graph[b][a]=d

import heapq
def dijkstra(s,graph,n):
    dist=[10**20 for i in range(n+1)]
    dist[s]=0
    pq=[]
    heapq.heapify(pq)
    heapq.heappush(pq,(0,s))
    while pq:
        x=heapq.heappop(pq)
        node,mini_dis=x[1],x[0]
        for point in graph[node].keys():
            w=graph[node][point]
            newlen=dist[node]+w
            if newlen<dist[point]:
                heapq.heappush(pq,(newlen,point))
                dist[point]=newlen
    return dist
Q,K=map(int,input().split())
P=dijkstra(K,graph,n)
for i in range(Q):
    x,y=map(int,input().split())
    print(P[x]+P[y])

Solution (Python):
from collections import deque
N = int(input())
graph = [[] for _ in range(N)]
for _ 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, K = map(int, input().split())
visited = [0] * N
visited[K - 1] = 1
q = deque([(K - 1, 0)])
while q:
    p, c = q.popleft()
    for dst, d in graph[p]:
        if not visited[dst]:
            visited[dst] = c + d
            q.append((dst, c + d))
for _ in range(Q):
    x, y = map(lambda n: int(n) - 1, input().split())
    print(visited[x] + visited[y])

Solution (Python):
from collections import deque
N = int(input())
graph = [[] for _ in range(N)]
for _ 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, K = map(int, input().split())
visited = [0] * N
visited[K - 1] = 1
q = deque([(K - 1, 0)])
while q:
    p, c = q.popleft()
    for dst, d in graph[p]:
        if not visited[dst]:
            visited[dst] = c + d
            q.append((dst, c + d))
for _ in range(Q):
    x, y = map(lambda n: int(n) - 1, input().split())
    print(visited[x] + visited[y])

Solution (Python):
N=int(input())
import sys
sys.setrecursionlimit(10**6)
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())
D=[-1]*N
D[K-1]=0
def dfs(start, nowd):
    to=T[start]
    for t in to:
        next_node,c=t
        if D[next_node]!=-1:
            continue
        nextd=nowd+c
        D[next_node]=nextd
        dfs(next_node, nextd)
dfs(K-1,0)
for i in range(Q):
    x,y=map(int, input().split())
    print(D[x-1]+D[y-1])

Solution (Python):
from collections import deque

N=int(input())
g=[[] for _ in range(N)]
visit=[0]*N
dist=[0]*N

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

    g[a].append([b,c])
    g[b].append([a,c])


Q,K=list(map(int,input().split()))
K-=1

q=deque([K])
visit[K]=1

while len(q)>0:
    p=q.popleft()
    
    for c,d in g[p]:
        if visit[c]==0:
            dist[c]=d+dist[p]
            visit[c]=1
            q.append(c)
    
for _ in range(Q):
    x,y=list(map(int,input().split()))
    x-=1
    y-=1
    print(dist[x]+dist[y])

Solution (Python):
from collections import deque

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

for _ 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, k = map(int, input().split())

distance = [float('inf') for _ in range(n)]
distance[k - 1] = 0

d = deque()
d.append(k - 1)
visited = set({})
while d:
    point = d.popleft()
    for index, value in graph[point]:
        distance[index] = min(distance[point] + value, distance[index])
        if index not in visited:
            d.append(index)
    visited.add(point)
    
for _ in range(q):
    x, y = map(int, input().split())
    print(distance[x - 1] + distance[y - 1])

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)


n=int(input())

c={}
tree=[set([]) for _ in range(n)]

for _ in range(n-1):
    i,j,k=map(int,input().split())
    i-=1
    j-=1
    tree[i].add(j)
    tree[j].add(i)
    c[(min(i,j),max(i,j))]=k

result=[]
q,k=map(int,input().split())

memo=[-1]*n

def DEF(z,cnt):
    global memo,tree,c
    memo[z]=cnt
    for item in tree[z]:
        if memo[item]==-1:
            DEF(item,cnt+c[(min(item,z),max(item,z))])

DEF(k-1,0)
result=[]
for item in range(q):
    a,b=map(int,input().split())
    result.append(memo[a-1]+memo[b-1])

for item in result:
    print(item)

Solution (Python):
import sys
import heapq


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


sys.setrecursionlimit(10 ** 9)


MOD = 10 ** 9 + 7


def dijkstra(start, n_nodes, edge):
    dist = [float("inf")] * n_nodes
    dist[start] = 0
    
    q = [(dist[start], start)]
    heapq.heapify(q)
    while q:
        
        d, i = heapq.heappop(q)
        
        
        if dist[i] < d:
            continue
        
        
        for cost, j in edge[i]:
            if dist[j] > dist[i] + cost:
                dist[j] = dist[i] + cost
                heapq.heappush(q, (dist[j], j))
    return dist


def main():
    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())
    D = dijkstra(K - 1, N, edge)
    for _ in range(Q):
        x, y = map(int, input().split())
        print(D[x - 1] + D[y - 1])


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

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())
dis = [float('inf')]*(n+1)
dis[k] = 0
que = deque(g[k])
while que:
    x,y  = que.popleft()
    if dis[x] == float('inf'):
        dis[x] = y
        for x_, y_ in g[x]:
            que.append((x_, dis[x]+y_))
    else:
        dis[x] = min(dis[x], y)

ans = []
for _ in range(q):
    x,y = map(int,input().split())
    ans.append(dis[x] + dis[y])
for a in ans:
    print(a)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
n=int(input())
l=[[] for i in range(n)]
C=[0]*n
for i in range(n-1):
    a,b,c=map(int,input().split())
    a-=1
    b-=1
    l[a].append([b,c])
    l[b].append([a,c])
def dfs(now,par,cost):
    C[now]=cost
    L=l[now]
    for i in range(len(L)):
        if L[i][0]==par:
            continue
        dfs(L[i][0],now,cost+L[i][1])
Q,K=map(int,input().split())
K-=1
dfs(K,K,0)
for i in range(Q):
    x,y=map(int,input().split())
    x-=1
    y-=1
    print(C[x]+C[y])

Solution (Python):
class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK
    
    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        """ 重み付き有向辺
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点の数
        """
        self.G = [[] for i in range(V)]  
        self._E = 0  
        self._V = V  

    @property
    def E(self):
        """ 辺数
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return self._E
    
    @property
    def V(self):
        """ 頂点数 """
        return self._V
    
    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1
        
    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す 
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短コストを格納したリスト。
                     到達不可の場合、値はfloat("inf")
        """
        import heapq
        que = []  
        d = [float("inf")] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  

        while len(que) != 0:
            cost, v = heapq.heappop(que)
            
            if d[v] < cost: continue

            for i in range(len(self.G[v])):
                
                e = self.G[v][i]  
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost  
                    heapq.heappush(que, (d[e.to], e.to))  
        return d

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

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

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

Solution (Python):
import sys
input = sys.stdin.readline
def main():
  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)]
  
  ki=[[]for _ in range(n)]
  for a,b,c in abc:
    ki[a-1].append([b-1,c])
    ki[b-1].append([a-1,c])
  kakutei=[0]*n
  kyori=[pow(10,14)]*n
  kyori[k-1]=0
  import heapq
  mikakutei=[[0,k-1]]
  heapq.heapify(mikakutei)
  while len(mikakutei)>0:
    k,i=heapq.heappop(mikakutei)
    if kakutei[i]==1:
      continue
    kakutei[i]=1
    l=ki[i]
    for li in l:
      if kakutei[li[0]]==0:
        kyori[li[0]]=min(kyori[li[0]],k+li[1])
        heapq.heappush(mikakutei,[kyori[li[0]],li[0]])
  for x,y in xy:
    print(kyori[x-1]+kyori[y-1])
    

if __name__=='__main__':
  main()

Solution (Python):
import sys
sys.setrecursionlimit(10**8)

N = int(input())

vertex = [{} for _ in range(N)]

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

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

d = [0 for i in range(N)]

def dfs(v1,v2):
    d[v2] = d[v1] + vertex[v1][v2]
    for v in vertex[v2]:
        if v == v1:
            continue
        dfs(v2,v)

for v in vertex[K-1].keys():
    dfs(K-1,v)

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

Solution (Python):
import sys
readline = sys.stdin.readline
from collections import deque

def main():
    N = int(readline())
    path = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b, c = map(int, readline().rstrip().split())
        path[a-1].append((b-1, c))
        path[b-1].append((a-1, c))
    Q, K = map(int, readline().rstrip().split())
    K -= 1

    dist = [-1] * N
    dist[K] = 0
    
    que = deque([K])
    while que:
        pre = que.popleft()
        for next, d in path[pre]:
            if dist[next] == -1:
                dist[next] = dist[pre] + d
                que.append(next)

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

if __name__ == '__main__':
    main()

Solution (Python):
import sys
readline = sys.stdin.readline
from collections import deque

def main():
    N = int(readline())
    path = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b, c = map(int, readline().rstrip().split())
        path[a-1].append((b-1, c))
        path[b-1].append((a-1, c))
    Q, K = map(int, readline().rstrip().split())
    K -= 1

    dist = [-1] * N
    dist[K] = 0
    for n, c in path[K]:
        dist[n] = c
        
    que = deque([(K, n) for n, c in path[K]])
    while que:
        pre, now = que.popleft()
        for next, d in path[now]:
            if next != pre:
                dist[next] = dist[now] + d
                que.append((now, next))

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

if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
G = [dict() for i in range(N)]
for i in range(N-1):
    a,b,c = map(int,input().split())
    G[a-1][b-1] = c
    G[b-1][a-1] = c

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

inf = 10**20
import heapq 



def Dijkstra(ad_dict,start): 
    distance = [inf for _ in range(N)] 
    previous = [inf for _ in range(N)] 
    distance[start] = 0
    hq = []
    heapq.heappush(hq, (0, start)) 
    while hq:
        temp_dist, prev = heapq.heappop(hq)
        if distance[prev] < temp_dist:
            
            continue
        for now, cost in ad_dict[prev].items():
            if (distance[prev] + cost) < distance[now]: 
                distance[now] = distance[prev] + cost 
                heapq.heappush(hq, (distance[now], now))
                previous[now] = prev
    return distance, previous 

def reconstruct_path(distance, previous, goal): 
    now = goal
    path = [goal]
    while previous[now] != inf: 
        path.append(previous[now])
        now = previous[now]
    return list(path[::-1]) 

D,_ = Dijkstra(G,K-1)
for i in range(Q):
    x,y = map(int,input().split())
    print(D[x-1]+D[y-1])

Solution (Python):
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)

    
    dfs(k - 1, -1, 0)

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


if __name__ == '__main__':
    resolve()