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
from collections import deque
input = sys.stdin.readline

def main():
    N = int(input())
    links = [[] for i in range(N+1)]
    for i in range(N-1):
        a, b, c = map(int, input().split())
        links[a].append([b, c])
        links[b].append([a, c])
    
    Q, K = map(int, input().split())

    check = [False] * (N+1)
    cost = [0] * (N+1)
    q = deque()
    q.append([K, 0])
    while len(q) > 0:
        node, now_cost = q.popleft()
        check[node] = True
        cost[node] = now_cost
        for n in links[node]:
            
            if not check[n[0]]:
                q.append([n[0], now_cost + n[1]])
    
    for i in range(Q):
        x, y = map(int, input().split())
        print(cost[x] + cost[y])

if __name__ == "__main__":
    main()

Solution (Python):



import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7

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())
que = deque()
que.append(k-1)
dist = [-1]*n
dist[k-1] = 0
while que:
    v = que.popleft()
    for x,c in g[v]:
        if dist[x] == -1:
            dist[x] = dist[v] + c
            que.append(x)

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

Solution (Python):



import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7

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())
que = deque()
que.append(k-1)
dist = [-1]*n
dist[k-1] = 0
while que:
    v = que.popleft()
    for x,c in g[v]:
        if dist[x] == -1:
            dist[x] = dist[v] + c
            que.append(x)

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

Solution (Python):



import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7

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

g = [[] for _ in range(n)]
for a,b,c in abc:
    g[a-1].append((b-1,c))
    g[b-1].append((a-1,c))

que = deque()
que.append(k-1)
dist = [-1]*n
dist[k-1] = 0
while que:
    v = que.popleft()
    for x,c in g[v]:
        if dist[x] == -1:
            dist[x] = dist[v] + c
            que.append(x)

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

Solution (Python):
N = int(input())
way = [[] for _ in range(N+1)]
depth = [float("inf")]*(N+1)
for _ in range(N - 1):
    a,b,c = map(int, input().split())
    way[a].append((b, c))
    way[b].append((a, c))

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

stack = []
stack.append((K, 0))

while stack:
    now, d = stack.pop()
    depth[now] = d
    for i, j in way[now]:
        if depth[i] < d+j:
            continue
        stack.append((i, d+j))

for x,y in xy:
    print(depth[x] + depth[y])

Solution (Python):
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque

from itertools import product

from itertools import permutations

from itertools import combinations

from itertools import accumulate
from bisect import bisect_left, bisect_right

import re







def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e18)
MOD = int(1e9)+7 


def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]


    

def main():
    N = i_inpl()
    G = defaultdict(dict)
    for _ in range(N-1):
        ai, bi, ci = l_inpl()
        ai, bi = ai-1, bi-1
        G[ai][bi] = ci
        G[bi][ai] = ci
    
    Q, K = l_inpl()
    K = K-1
    qlist = [l_inpl() for _ in range(Q)]

    cost = [INF] * N
    cost[K] = 0

    
    queue = deque([K])
    while queue:
        s = queue.pop()
        for t in G[s]:
            if cost[t] > cost[s] + G[s][t]:
                cost[t] = cost[s] + G[s][t]
                queue.append(t)
    
    for xi, yi in qlist:
        print(cost[xi-1]+cost[yi-1])


 
if __name__ == "__main__":
    main()

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

N = int(input())
E = {n: set() for n in range(N)}

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

def m():
    Q, K = map(int, input().split())
    K -= 1
    dist = [-1] * N
    already = set()
    que = queue.Queue()
    dist[K] = 0
    que.put(K)
    while not que.empty():
        now = que.get()
        out = E[now]
        for n, c in out:
            if dist[n] != -1:
                continue
            dist[n] = dist[now] + c        
            que.put(n)
    
    for _ in range(Q):
        x, y = map(int, input().split())
        x -= 1
        y -= 1
        print(dist[x] + dist[y])

if __name__ == "__main__":
    m()

Solution (Python):
import queue

N = int(input())
E = {n: set() for n in range(N)}

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

def m():
    Q, K = map(int, input().split())
    K -= 1
    dist = [-1] * N
    already = set()
    que = queue.Queue()
    dist[K] = 0
    que.put(K)
    while not que.empty():
        now = que.get()
        out = E[now]
        for n, c in out:
            if dist[n] != -1:
                continue
            dist[n] = dist[now] + c        
            que.put(n)
    
    res = ""
    for _ in range(Q):
        x, y = map(int, input().split())
        x -= 1
        y -= 1
        res += str(dist[x] + dist[y]) + "\n"
    
    print(res)

if __name__ == "__main__":
    m()

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

N = int(input())
E = {n: set() for n in range(N)}

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

Q, K = map(int, input().split())
K -= 1
dist = [-1] * N
already = set()
que = queue.Queue()
dist[K] = 0
que.put(K)
while not que.empty():
    now = que.get()
    out = E[now]
    for n, c in out:
        if dist[n] != -1:
            continue
        dist[n] = dist[now] + c        
        que.put(n)

res = ""
for _ in range(Q):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    res += str(dist[x] + dist[y]) + "\n"

print(res)

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

N = int(input())
E = {n: set() for n in range(N)}

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

def m():
    Q, K = map(int, input().split())
    K -= 1
    dist = [-1] * N
    already = set()
    que = queue.Queue()
    dist[K] = 0
    que.put(K)
    while not que.empty():
        now = que.get()
        out = E[now]
        for n, c in out:
            if dist[n] != -1:
                continue
            dist[n] = dist[now] + c        
            que.put(n)
    
    res = ""
    for _ in range(Q):
        x, y = map(int, input().split())
        x -= 1
        y -= 1
        res += str(dist[x] + dist[y]) + "\n"
    
    print(res)

if __name__ == "__main__":
    m()

Solution (Python):
import queue

N = int(input())
E = {n: set() for n in range(N)}

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

Q, K = map(int, input().split())
K -= 1
dist = [-1] * N
already = set()
que = queue.Queue()
que.put((K, 0))
while not que.empty():
    now, d = que.get()
    already.add(now)
    dist[now] = d
    out = E[now]
    for n, c in out:
        if n in already:
            continue
        que.put((n, d + c))

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

Solution (Python):

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

n = int(input())

T = [{} for _ in range(n)]
for _ in range(n-1):
    v1,v2,d = map(int, input().split())
    v1,v2 = v1-1,v2-1
    T[v1][v2] = d
    T[v2][v1] = d

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

depth = [-1]*n
que = deque()
que.append(k-1)
while que:
    p = que.popleft()
    if depth[p]<0: depth[p] = 0
    for c in T[p].keys():
        if depth[c]>=0: continue
        depth[c] = depth[p] + T[p][c]
        que.append(c)

for _ in range(q):
    v1,v2 = map(int, input().split())
    print(depth[v1-1]+depth[v2-1])

Solution (Python):

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

n = int(input())

T = [{} for _ in range(n)]
for _ in range(n-1):
    v1,v2,d = map(int, input().split())
    T[v1-1][v2-1] = d
    T[v2-1][v1-1] = d

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

visit = [False]*n
depth = [0]*n
que = deque()
que.append(k-1)
while que:
    p = que.popleft()
    visit[p] = True
    for c in T[p].keys():
        if visit[c]: continue
        depth[c] = depth[p] + T[p][c]
        que.append(c)

for _ in range(q):
    v1,v2 = map(int, input().split())
    print(depth[v1-1]+depth[v2-1])

Solution (Python):


from collections import deque

n = int(input())

T = [{} for _ in range(n)]
for _ in range(n-1):
    v1,v2,d = map(int, input().split())
    T[v1-1][v2-1] = d
    T[v2-1][v1-1] = d

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

visit = [False]*n
depth = [0]*n
que = deque()
que.append(k-1)
while que:
    p = que.popleft()
    visit[p] = True
    for c in T[p].keys():
        if visit[c]: continue
        depth[c] = depth[p] + T[p][c]
        que.append(c)

for _ in range(q):
    v1,v2 = map(int, input().split())
    print(depth[v1-1]+depth[v2-1])

Solution (Python):


from collections import deque

n = int(input())

T = [{} for _ in range(n)]
for _ in range(n-1):
    v1,v2,d = map(int, input().split())
    T[v1-1][v2-1] = d
    T[v2-1][v1-1] = d

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

visit = [False]*n
depth = [0]*n
que = deque([[-1,k-1,0]])
while que:
    p,c,d = que.popleft()
    if visit[c]: continue
    visit[c] = True
    depth[c] = d
    if p>=0: depth[c] += depth[p]
    for cc in T[c].keys():
        if not visit[cc]: que.append([c,cc,T[c][cc]])

for _ in range(q):
    v1,v2 = map(int, input().split())
    print(depth[v1-1]+depth[v2-1])

Solution (Python):


n = int(input())

T = [{} for _ in range(n)]
for _ in range(n-1):
    v1,v2,d = map(int, input().split())
    T[v1-1][v2-1] = d
    T[v2-1][v1-1] = d

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

visit = [False]*n
depth = [0]*n
stack = [[-1,k-1,0]]
while stack:
    p,c,d = stack.pop()
    if visit[c]: continue
    visit[c] = True
    depth[c] = d
    if p>=0: depth[c] += depth[p]
    for cc in T[c].keys():
        if not visit[cc]: stack.append([c,cc,T[c][cc]])

for _ in range(q):
    v1,v2 = map(int, input().split())
    print(depth[v1-1]+depth[v2-1])

Solution (Python):


n = int(input())

T = [[] for _ in range(n)]
for _ in range(n-1):
    v1,v2,d = map(int, input().split())
    v1,v2 = v1-1,v2-1
    T[v1].append([v1,v2,d])
    T[v2].append([v2,v1,d])

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

visit = [False]*(n)
depth = [0]*(n)
stack = [[-1,k-1,0]]
while stack:
    p,c,d = stack.pop()
    if visit[c]: continue
    visit[c] = True
    depth[c] = d
    if p>=0: depth[c] += depth[p]
    for pp,cc,dd in T[c]:
        if not visit[cc]: stack.append([pp,cc,dd])

for _ in range(q):
    v1,v2 = map(int, input().split())
    print(depth[v1-1]+depth[v2-1])

Solution (Python):


n = int(input())

T = [[] for _ in range(n+1)]
for _ in range(n-1):
    v1,v2,d = map(int, input().split())
    T[v1].append([v1,v2,d])
    T[v2].append([v2,v1,d])

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

visit = [False]*(n+1)
depth = [0]*(n+1)
stack = [[0,k,0]]
while stack:
    p,c,d = stack.pop()
    if visit[c]: continue
    visit[c] = True
    depth[c] = depth[p] + d
    for pp,cc,dd in T[c]:
        if not visit[cc]: stack.append([pp,cc,dd])

for _ in range(q):
    v1,v2 = map(int, input().split())
    print(depth[v1]+depth[v2])

Solution (Python):


n = int(input())

T = [None]*(n+1)
for _ in range(n-1):
    v1,v2,d = map(int, input().split())
    if(T[v1] is None): T[v1] = [[v1,v2,d]]
    else: T[v1].append([v1,v2,d])
    if(T[v2] is None): T[v2] = [[v2,v1,d]]
    else: T[v2].append([v2,v1,d])

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

visit = [False]*(n+1)
depth = [0]*(n+1)
stack = [[0,k,0]]
while stack:
    p,c,d = stack.pop()
    if visit[c]: continue
    visit[c] = True
    depth[c] = depth[p] + d
    for pp,cc,dd in T[c]:
        if not visit[cc]: stack.append([pp,cc,dd])

for _ in range(q):
    v1,v2 = map(int, input().split())
    print(depth[v1]+depth[v2])

Solution (Python):

 
n = int(input())
 
T = [None]*(n+1)
for _ in range(n-1):
    v1,v2,d = map(int, input().split())
    if(T[v1] is None): T[v1] = [[v1,v2,d]]
    else: T[v1].append([v1,v2,d])
    if(T[v2] is None): T[v2] = [[v2,v1,d]]
    else: T[v2].append([v2,v1,d])

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

depth = [0]*(n+1)
visit = [False]*(n+1)
depth[k] = 0
visit[k] = True
stack = T[k]
while stack:
    p,c,d = stack.pop()
    if visit[c]: continue
    visit[c] = True
    depth[c] = depth[p] + d
    for pp,cc,dd in T[c]:
        if not visit[cc]: stack.append([pp,cc,dd])
 
for _ in range(q):
    v1,v2 = map(int, input().split())
    print(depth[v1]+depth[v2])

Solution (Python):


n = int(input())

T = [None]*(n+1)
for _ in range(n-1):
    v1,v2,d = map(int, input().split())
    if(T[v1] is None): T[v1] = [[v1,v2,d]]
    else: T[v1].append([v1,v2,d])
    if(T[v2] is None): T[v2] = [[v2,v1,d]]
    else: T[v2].append([v2,v1,d])

depth = [0]*(n+1)

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

is_visit = [False]*(n+1)
p,c,d = 0,k,0
depth[c] = d
is_visit[c] = True
stack = T[c]
while stack:
    p,c,d = stack.pop()
    if is_visit[c]: continue
    is_visit[c] = True
    depth[c] = depth[p] + d
    for pp,cc,dd in T[c]:
        if not is_visit[cc]: stack.append([pp,cc,dd])

for _ in range(q):
    v1,v2 = map(int, input().split())
    print(depth[v1]+depth[v2])

Solution (Python):
n=int(input())
abc=[list(map(int,input().split())) for _ in [0]*(n-1)]
q,k=map(int,input().split())
xy=[list(map(int,input().split())) for _ in [0]*q]

g=[[] for _ in [0]*n]
[g[b-1].append([a-1,c]) for a,b,c in abc]
[g[a-1].append([b-1,c]) for a,b,c in abc]

inf=10**15
dist=[None for _ in [0]*n]
dist[k-1]=0
q=[k-1]
while q:
    i=q.pop()
    gg=g[i]
    for j,k in gg:
        if dist[j]==None:
            dist[j]=dist[i]+k
            q.append(j)
for x,y in xy:
    print(dist[x-1]+dist[y-1])

Solution (Python):
import itertools
import math

def dfs(N,E,start):
    d = [-1] * (N + 1)
    d[start] = 0
    q = [start]
    while q:
        now = q.pop()
        vertexes = E[now]
        for to in vertexes:
            if d[to] == -1:
                d[to] = d[now] + E[now][to]
                q.append(to)
    return d
N = int(input())
E = [{} for _ in range(N + 1)]
for _ in range(N-1):
    a,b,c = map(int, input().split(" "))
    E[a][b] = c
    E[b][a] = c

Q, K = map(int, input().split(" "))
d = dfs(N,E,K)
AB = [list(map(int, input().split(" "))) for _ in range(Q)]
for a,b in AB:
    print(d[a] + d[b])

Solution (Python):
N = int(input())
ABC = [list(map(int,input().split())) for _ in [0]*(N-1)]
Q,K = map(int,input().split())
XY = [list(map(int,input().split())) for _ in [0]*Q]

E = [{} for _ in [0]*N]
for a,b,c in ABC:
    E[a-1][b-1] = c
    E[b-1][a-1] = c

def dist_dfs_tree(N,E,start):
    d = [-1]*N
    d[start] = 0
    q = [start]
    while q:
        i = q.pop()
        ci = d[i]
        for j,cj in E[i].items():
            if d[j] !=-1:continue
            d[j] = ci+cj
            q.append(j)
    return d

d = dist_dfs_tree(N,E,K-1)
for x,y in XY:
    print(d[x-1]+d[y-1])

Solution (Python):
import heapq
WHITE = 0
GRAY = 1
BLACK = 2
INFTY = 10**16
def dijkstra(s, VC):
    color = [WHITE for i in range(N+1)]
    d = [INFTY for i in range(N+1)]
    d[s] = 0
    pq = []
    heapq.heappush(pq, (0, s))

    while len(pq) != 0:
        u = heapq.heappop(pq)[1]
        color[u] = BLACK

        for v, c in VC[u]:
            if color[v] != BLACK:
                if d[u] + c < d[v]:
                    d[v] = d[u] + c
                    color[v] = GRAY
                    heapq.heappush(pq, (d[v], v))

    return d

N = int(input())
V = [[] for i in range(N+1)]
for i in range(N-1):
    a, b, c = map(int, input().split())
    V[a].append([b, c])
    V[b].append([a, c])
Q, K = map(int, input().split())
d = dijkstra(K, V)
for i in range(Q):
    x, y = map(int, input().split())
    print(d[x] + d[y])

Solution (Python):
import sys
input=sys.stdin.readline
n=int(input())
G=[[] for i 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=k-1
stack=[k]
dis=[-1]*n
dis[k]=0
while len(stack)>0:
    now=stack.pop()
    d=dis[now]
    for i in G[now]:
        if dis[i[0]]==-1:
            dis[i[0]]=d+i[1]
            stack.append(i[0])
for i in range(q):
    x,y=map(int,input().split())
    x=x-1
    y=y-1
    print(dis[x]+dis[y])

Solution (Python):
import sys
input=sys.stdin.readline
n=int(input())
G=[[] for i in range(n)]
for i in range(n-1):
    a,b,c=[int(v)-1 for v in input().split()]
    c+=1
    G[a].append((b,c))
    G[b].append((a,c))
q,k=[int(v) for v in input().split()]
k=k-1
stack=[k]
dis=[-1]*n
dis[k]=0
while stack!=[]:
    now=stack.pop()
    d=dis[now]
    for i in G[now]:
        if dis[i[0]]==-1:
            dis[i[0]]=d+i[1]
            stack.append(i[0])
for i in range(q):
    x,y=[int(v)-1 for v in input().split()]
    print(dis[x]+dis[y])

Solution (Python):
n=int(input())
G=[[] for i in range(n)]
for i in range(n-1):
    a,b,c=[int(v)-1 for v in input().split()]
    c+=1
    G[a].append((b,c))
    G[b].append((a,c))
q,k=[int(v) for v in input().split()]
k=k-1
stack=[k]
dis=[-1]*n
dis[k]=0
while stack!=[]:
    now=stack.pop()
    d=dis[now]
    for i in G[now]:
        if dis[i[0]]==-1:
            dis[i[0]]=d+i[1]
            stack.append(i[0])
for i in range(q):
    x,y=[int(v)-1 for v in input().split()]
    print(dis[x]+dis[y])

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

n = int(input())
connect_list = [[] for i in range(n)]
for i in range(n-1):
    a, b, c = [ int(v)-1 for v in input().split() ]
    c += 1
    connect_list[a].append((b,c))
    connect_list[b].append((a,c))


q, k = [ int(v) for v in input().split() ]
k -= 1

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

searching_list = [k]

while searching_list != []:

    new_search_list = []
    for i in searching_list:
        for j in connect_list[i]:
            x, y = j
            if shortest_list[x] == -1:
                shortest_list[x] = y + shortest_list[i]
                new_search_list.append(x)
    searching_list = new_search_list


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

Solution (Python):
n=int(input())
G=[[] for i 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=k-1
stack=[k]
dis=[-1]*n
dis[k]=0
while stack!=[]:
    new=[]
    for j in stack:
        d=dis[j]
        for i in G[j]:
            if dis[i[0]]==-1:
                dis[i[0]]=d+i[1]
                new.append(i[0])
    stack=new
for i in range(q):
    x,y=map(int,input().split())
    x=x-1
    y=y-1
    print(dis[x]+dis[y])

Solution (Python):
n=int(input())
G=[[] for i 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=k-1
stack=[k]
dis=[-1]*n
dis[k]=0
while stack!=[]:
    now=stack.pop()
    d=dis[now]
    for i in G[now]:
        if dis[i[0]]==-1:
            dis[i[0]]=d+i[1]
            stack.append(i[0])
for i in range(q):
    x,y=map(int,input().split())
    x=x-1
    y=y-1
    print(dis[x]+dis[y])

Solution (Python):
n=int(input())
G=[[] for i 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=k-1
stack=[k]
dis=[-1]*n
dis[k]=0
from collections import deque
stack=deque(stack)
while len(stack)>0:
    now=stack.pop()
    d=dis[now]
    for i in G[now]:
        if dis[i[0]]==-1:
            dis[i[0]]=d+i[1]
            stack.append(i[0])
for i in range(q):
    x,y=map(int,input().split())
    x=x-1
    y=y-1
    print(dis[x]+dis[y])

Solution (Python):
n=int(input())
G=[[] for i 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=k-1
stack=[k]
dis=[-1]*n
dis[k]=0
ls=1
while ls>0:
    now=stack.pop()
    ls-=1
    d=dis[now]
    for i in G[now]:
        if dis[i[0]]==-1:
            dis[i[0]]=d+i[1]
            stack.append(i[0])
            ls+=1
for i in range(q):
    x,y=map(int,input().split())
    x=x-1
    y=y-1
    print(dis[x]+dis[y])

Solution (Python):
n=int(input())
G=[[] for i 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=k-1
stack=[k]
dis=[-1]*n
dis[k]=0
while len(stack)>0:
    now=stack.pop()
    d=dis[now]
    for i in G[now]:
        if dis[i[0]]==-1:
            dis[i[0]]=d+i[1]
            stack.append(i[0])
for i in range(q):
    x,y=map(int,input().split())
    x=x-1
    y=y-1
    print(dis[x]+dis[y])

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
abc = [LIST() for _ in range(N-1)]
graph = defaultdict(list)
for a, b, c in abc:
	graph[a-1].append((b-1, c))
	graph[b-1].append((a-1,c))

Q, K = MAP()
xy = [LIST() for _ in range(Q)]

dist = [-1]*N  
dist[K-1] = 0

def dfs(node):
	for to, cost in graph[node]:
		if dist[to] != -1:
			continue
		dist[to] = dist[node]+cost
		dfs(to)
dfs(K-1)


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

Solution (Python):
import sys
from collections import deque


fin = sys.stdin.readline
N = int(fin())
adj = [[] for _ in range(N)]
w = {}
for _ in range(N - 1):
    a, b, c = [int(elem) for elem in fin().split()]
    a -= 1
    b -= 1
    adj[a].append(b)
    adj[b].append(a)
    w[a, b] = c
    w[b, a] = c

Q, K = [int(elem) for elem in fin().split()]
K -= 1
queries = tuple(tuple(int(elem) - 1 for elem in fin().split()) for _ in range(Q))
dist_from_root = {K: 0}
nodes = deque()
nodes.append(K)
while nodes:
    node = nodes.popleft()
    dist = dist_from_root[node]
    for neighbor in adj[node]:
        if neighbor not in dist_from_root:
            dist_from_root[neighbor] = dist + w[node, neighbor]
            nodes.append(neighbor)

for x, y in queries:
    print(dist_from_root[x] + dist_from_root[y])

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

n = int(input())
dat =[]
link = []
for i in range(n+1):
    link.append([])
cost = [-1] * (n + 1)

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

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

for i in range(q):
    x, y = map(int, input().split())
    dat_q.append((x,y))



def search(curcost, current):
    
    cost[current] = curcost
    for npos, ncost in link[current]:
        if cost[npos] != -1:
            
            continue
        search(curcost + ncost, npos)

search(0, k)


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

Solution (Python):
import numpy as np
from collections import defaultdict
from heapq import heappush, heappop


def djkstra_adj_list(adj_list, src):
    dist = defaultdict(lambda: np.inf)
    dist[src] = 0

    prev = defaultdict(lambda: None)

    queue = []
    heappush(queue, (dist[src], src))

    while len(queue) > 0:
        dist_u, u = heappop(queue)
        vs = adj_list[u]
        for v, weight in vs:
            alt = dist_u + weight
            if alt < dist[v]:
                dist[v] = alt
                prev[v] = u
                heappush(queue, (alt, v))

    return dist, prev


def djkstra_adj_mat(adj_mat, src):
    dist = defaultdict(lambda: np.inf)
    dist[src] = 0

    prev = defaultdict(lambda: None)

    queue = []
    heappush(queue, (dist[src], src))

    while len(queue) > 0:
        dist_u, u = heappop(queue)
        vs = np.argwhere(adj_mat[u] > 0).flatten()
        for v in vs:
            weight = adj_mat[u, v]
            alt = dist_u + weight
            if alt < dist[v]:
                dist[v] = alt
                prev[v] = u
                heappush(queue, (alt, v))

    return dist, prev


def main():
    N = int(input())

    adj_list = [[] for _ in range(N)]

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

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

    dist, prev = djkstra_adj_list(adj_list, K)

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

    for a in ans:
        print(a)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict
from heapq import heappush, heappop


def solve(n_query, q_query, k):
    d = defaultdict(list)
    for a, b, c in n_query:
        d[a].append((c, b))
        d[b].append((c, a))

    from_k = dijkstra(n+1, d, k)
    ans = []
    for x, y in q_query:
        x_to_k = from_k[x]
        k_to_y = from_k[y]

        ans.append(x_to_k + k_to_y)
    

    return ans


def dijkstra(vertex, g, sp):
    d = [float('inf')] * vertex
    d[sp] = 0
    heap = [(d[sp], sp)]

    while heap:
        du, u = heappop(heap)
        for length, v in g[u]:

            if d[v] > du + length:
                d[v] = du + length
                heappush(heap, (d[v], v))
    return d


if __name__ == '__main__':
    n = int(input())
    par, rank = [-1]*(n+1), [0]*(n+1)
    diff_weight = [0]*(n+1)
    is_via_root = [1]*(n+1)
    n_query = []
    q_query = []

    for _ in range(n-1):
        a, b, c = map(int, input().split())
        n_query.append((a, b, c))
    q, k = map(int, input().split())
    for _ in range(q):
        x, y = map(int, input().split())
        q_query.append((x, y))

    ans = solve(n_query, q_query, k)
    for a in ans:
        print(a)

Solution (Python):
import heapq

N = int(input())
graph = [[] for i in range(N+1)]
visited = [False] * (N+1)
cost = [10**20 for i in range(N+1)]

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

for cr in graph[K]:
    heapq.heappush(q, cr)
visited[K] = True
cost[K] = 0

while q:
    c, r = heapq.heappop(q)
    
    if not visited[r]:
        visited[r] = True
        cost[r] = c
        
        for c_n, r_n in graph[r]:
            if not visited[r_n]:
                heapq.heappush(q, (c+c_n, r_n))
                
for i in range(Q):
    x, y = map(int, input().split())
    print(cost[x] + cost[y])

Solution (Python):




import sys

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

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

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

d=[0]*n
visited=[False]*n

def dfs(s,p):
    visited[s]=True
    for c,v in edge[s]:
        if visited[v] or p==v:continue
        d[v]=c+d[s]
        visited[v]=True
        dfs(v,s)
    return 


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

Solution (Python):



import sys

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

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

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

d=[0]*n
visited=[False]*n

def dfs(s,p):
    visited[s]=True
    for c,v in edge[s]:
        if visited[v] or p==v:continue
        d[v]=c+d[s]
        visited[v]=True
        dfs(v,s)
    return 


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