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



def main():
    from collections import defaultdict
    from collections import deque
    import sys

    n = int(input())
    graph = [defaultdict(int) for _ in range(n)]
    visited = [False for _ in range(n)]
    dist = [float('inf') for _ in range(n)]
    lines = sys.stdin.readlines()

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

    q, k = map(int, lines[n - 1].split())
    k -= 1
    dist[k] = 0
    d = deque()
    d.append(k)

    while d:
        di = d.popleft()
        visited[di] = True

        for bi, ci in graph[di].items():
            if visited[bi]:
                continue

            dist[bi] = dist[di] + ci
            d.append(bi)

    ans = [0 for _ in range(q)]

    for j in range(q):
        xi, yi = map(int, lines[n + j].split())
        xi -= 1
        yi -= 1
        ans[j] = dist[xi] + dist[yi]

    print('\n'.join(map(str, ans)))


if __name__ == '__main__':
    main()

Solution (Python):



def main():
    from collections import defaultdict
    from collections import deque

    n = int(input())
    graph = [defaultdict(int) for _ in range(n)]
    visited = [False for _ in range(n)]
    dist = [float('inf') for _ in range(n)]

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

    q, k = map(int, input().split())
    k -= 1
    dist[k] = 0
    d = deque()
    d.append(k)

    while d:
        di = d.popleft()
        visited[di] = True

        for bi, ci in graph[di].items():
            if visited[bi]:
                continue

            dist[bi] = dist[di] + ci
            d.append(bi)

    ans = [0 for _ in range(q)]

    for j in range(q):
        xi, yi = map(int, input().split())
        xi -= 1
        yi -= 1
        ans[j] = dist[xi] + dist[yi]

    print('\n'.join(map(str, ans)))


if __name__ == '__main__':
    main()

Solution (Python):



def main():
    from collections import defaultdict
    from collections import deque

    n = int(input())
    graph = [defaultdict(int) for _ in range(n)]
    visited = [False for _ in range(n)]
    dist = [0 for _ in range(n)]

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

    q, k = map(int, input().split())
    k -= 1
    dist[k] = 0
    d = deque()
    d.append(k)

    while d:
        di = d.popleft()
        visited[di] = True

        for bi, ci in graph[di].items():
            if visited[bi]:
                continue

            dist[bi] = dist[di] + ci
            d.append(bi)

    for j in range(q):
        xi, yi = map(int, input().split())
        xi -= 1
        yi -= 1
        print(dist[xi] + dist[yi])


if __name__ == '__main__':
    main()

Solution (Python):



def main():
    from collections import defaultdict
    from collections import deque

    n = int(input())
    graph = [defaultdict(int) for _ in range(n)]
    visited = [False for _ in range(n)]
    dist = [float('inf') for _ in range(n)]

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

    q, k = map(int, input().split())
    k -= 1
    dist[k] = 0
    d = deque()
    d.append(k)

    while d:
        di = d.popleft()
        visited[di] = True

        for bi, ci in graph[di].items():
            if visited[bi]:
                continue

            dist[bi] = dist[di] + ci
            d.append(bi)

    for j in range(q):
        xi, yi = map(int, input().split())
        xi -= 1
        yi -= 1
        print(dist[xi] + dist[yi])


if __name__ == '__main__':
    main()

Solution (Python):



def main():
    from collections import defaultdict
    from collections import deque

    n = int(input())
    graph = [defaultdict(int) for _ in range(n)]
    visited = [False for _ in range(n)]
    dist = [float('inf') for _ in range(n)]

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

    q, k = map(int, input().split())
    k -= 1
    dist[k] = 0
    d = deque()
    d.append(k)

    while d:
        di = d.popleft()
        visited[di] = True

        for bi, ci in graph[di].items():
            if visited[bi]:
                continue

            dist[bi] = dist[di] + ci
            d.append(bi)

    for j in range(q):
        xi, yi = map(int, input().split())
        xi -= 1
        yi -= 1
        print(dist[xi] + dist[yi])


if __name__ == '__main__':
    main()

Solution (Python):

n = int(input())
edges = {}
dist = {}
con = {}

for i in range(n-1):
  a, b, c = map(int, input().split())
  edges[frozenset([a, b])] = c
  if a not in con:
    con[a] = {}
  if b not in con:
    con[b] = {}
  con[a][b] = True
  con[b][a] = True

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


dist[k] = 0
frontier = [k]
while len(dist.keys()) != n:
  frontier_new = []
  for f in frontier:
    for neigh in con[f]:
      if con[f][neigh]:
        dist[neigh] = dist[f] + edges[frozenset([neigh, f])]
        frontier_new.append(neigh)
        con[f][neigh] = False
        con[neigh][f] = False
  frontier = frontier_new[:]

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

Solution (Python):

n = int(input())
edges = {}
dist = {}
con = {}

for i in range(n-1):
  a, b, c = map(int, input().split())
  edges[frozenset([a, b])] = c
  if a not in con:
    con[a] = {}
  if b not in con:
    con[b] = {}
  con[a][b] = True
  con[b][a] = True

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


dist[k] = 0
frontier = [k]
while len(dist.keys()) != n:
  frontier_new = []
  for f in frontier:
    for neigh in con[f]:
      if con[f][neigh]:
        dist[neigh] = dist[f] + edges[frozenset([neigh, f])]
        frontier_new.append(neigh)
        con[f][neigh] = False
        con[neigh][f] = False
  frontier = frontier_new[:]

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

Solution (Python):
from heapq import heappop,heappush
def dijkstra(s):
    d = [float("inf")]*n
    used = [True]*n
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heappush(edgelist,e)
    while len(edgelist):
        short_edge = heappop(edgelist)
        if not used[short_edge[1]]:
            continue
        v = short_edge[1]
        d[v] = short_edge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                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):
    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)
for i in range(q):
    x,y = map(int,input().split())
    print(d[x-1]+d[y-1])

Solution (Python):

import sys

sys.setrecursionlimit(300000)

def dfs(idx, visited, conn, d, cur):
    visited[idx] = True
    for nex in conn[idx]:
        if not visited[nex[0]]:
            d[nex[0]] = cur + nex[1]
            d = dfs(nex[0], visited, conn, d, cur + nex[1])
    return d


def solve(N: int, A: "List[int]", B: "List[int]", C: "List[int]", Q: int, K: int, x: "List[int]", y: "List[int]"):

    conn = [[] for _ in range(N)]
    for j in range(N - 1):
        a = A[j] - 1
        b = B[j] - 1
        conn[a].append([b, C[j]])
        conn[b].append([a, C[j]])
    visited = [False] * N
    d = [0] * N
    d = dfs(K - 1, visited, conn, d, 0)
    for q in range(Q):
        s = x[q] - 1
        t = y[q] - 1
        ret = d[s] + d[t]
        print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    a = [int()] * (N-1)  
    b = [int()] * (N-1)  
    c = [int()] * (N-1)  
    for i in range(N-1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
    Q = int(next(tokens))  
    K = int(next(tokens))  
    x = [int()] * (Q)  
    y = [int()] * (Q)  
    for i in range(Q):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, a, b, c, Q, K, x, y)

if __name__ == '__main__':
    main()

Solution (Python):
n=int(input())
g=[[] for i in range(1+n)]
v=[0]*(1+n)
dist=[0]*(1+n)
for i in range(n-1):
    a,b,c=map(int,input().split())
    g[a].append([b,c])
    g[b].append([a,c])

def dfs(p):  
    while p:
        cur, depth=p.pop()
        v[cur]=1
        dist[cur]=depth
        for nb in g[cur]:
            if v[nb[0]]==0:
                p.append([nb[0],depth+nb[1]])
    return

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

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

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

def dfs(l,d,k):
  for i in l[k]:
    if d[i[0]]==-1:
      d[i[0]]=d[k]+i[1]
      dfs(l,d,i[0])

n=int(input())
l=[[] for i in range(n)]
for i in range(n-1):
  a,b,c=map(int,input().split())
  l[a-1].append([b-1,c])
  l[b-1].append([a-1,c])
q,k=map(int,input().split())
d=[-1 for i in range(n)]
d[k-1]=0
dfs(l,d,k-1)
L=[list(map(int,input().split())) for i in range(q)]
for i in range(q):
  print(d[L[i][0]-1]+d[L[i][1]-1])

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
N=int(input())

NODES={}
for i in range(N-1):
    a,b,c=map(int,input().split())
    if not a in NODES: NODES[a] = []
    if not b in NODES: NODES[b] = []
    NODES[a].append((b, c))
    NODES[b].append((a, c))

Q,K=map(int,input().split())
MP=[-1]*(N+1)
MP[K]=0
def dfs(k):
    for i, c in NODES[k]:
        if MP[i] == -1:
            MP[i] = MP[k] + c
            dfs(i)

dfs(K)

for l,r in [tuple(map(int,input().split())) for _ in range(Q)]:
    print(MP[l]+MP[r])

Solution (Python):
import sys
from collections import deque

N=input()

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

Q,K=map(int, sys.stdin.readline().split())

question=[ map(int, sys.stdin.readline().split())  for i in range(Q) ] 

Visit=[ None for i in range(N+1) ] 
Visit[K]=0

q=deque()
q.append(K)


while q:
	fro=q.popleft()
	for to,cost in nl[fro]:
		if Visit[to] is None:
			Visit[to]=Visit[fro]+cost
			q.append(to)


for x, y in question:
	print Visit[x]+Visit[y]

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
List = [[] for _ in range(N)]
ans = [-1]*N
for i in range(N-1):
    a, b, c = map(int, input().split())
    List[a-1].append((b-1, c))
    List[b-1].append((a-1, c))
Q, K = map(int, input().split())
queue = [K-1]
ans[K-1] = 0
while queue:
    edge = queue.pop()
    for node in List[edge]:
        index, cost = node
        if ans[index]>0:
            continue
        ans[index] = ans[edge]+cost
        queue.append(index)
for i in range(Q):
    x, y = map(int, input().split())
    print(ans[x-1]+ans[y-1])

Solution (Python):
import collections
N = int(input())
List = [[] for _ in range(N)]
ans = [-1]*N
for i in range(N-1):
    a, b, c = map(int, input().split())
    List[a-1].append((b-1, c))
    List[b-1].append((a-1, c))
Q, K = map(int, input().split())
queue = collections.deque([K-1])
ans[K-1] = 0
while queue:
    edge = queue.pop()
    for node in List[edge]:
        index, cost = node
        if ans[index]>0:
            continue
        ans[index] = ans[edge]+cost
        queue.append(index)
for i in range(Q):
    x, y = map(int, input().split())
    print(ans[x-1]+ans[y-1])

Solution (Python):
N = int(input())
List = [[] for _ in range(N)]
ans = [-1]*N
for i in range(N-1):
    a, b, c = map(int, input().split())
    List[a-1].append((b-1, c))
    List[b-1].append((a-1, c))
Q, K = map(int, input().split())
queue = [K-1]
ans[K-1] = 0
while queue:
    edge = queue.pop()
    for node in List[edge]:
        index, cost = node
        if ans[index]>0:
            continue
        ans[index] = ans[edge]+cost
        queue.append(index)
for i in range(Q):
    x, y = map(int, input().split())
    print(ans[x-1]+ans[y-1])

Solution (Python):
import heapq


N = int(input())
tree = {i+1:[] for i in range(N)}
route = [10**20 for i in range(N+1)]
visited = [False for i in range(N+1)]

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

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

route[K], visited[K] = 0, True
queue = tree[K]

while len(queue):
    c, r = heapq.heappop(queue)

    if not visited[r]:
         visited[r], route[r] = True, c
         for cost, next_r in tree[r]:
             if not visited[next_r]:
                 heapq.heappush(queue, (route[r]+cost, next_r))

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

Solution (Python):
def dfs(i, V, E):
    S = [i]
    while(len(S) > 0):
        vi = S.pop()
        d = V[vi]
        for j, value in E[vi].items():
            if V[j] > value + d:
                V[j] = value + d
                S.append(j)
    return V

INF = 10 ** 14
n = int(input())
V = [INF for _ in range(n + 1)]
E = [{} for _ in range(n + 1)]
for i in range(n - 1):
    ai, bi, ci = map(int, input().split())
    E[ai][bi] = ci
    E[bi][ai] = ci

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

V = dfs(k, V, E)
for i in range(q):
    x, y = z[i]
    print(V[x] + V[y])

Solution (Python):











import sys
import heapq
input=sys.stdin.readline
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [input() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')


def main():
    
    def dijkstra(start, edge):
        costs=[inf]*N
        costs[start]=0
        hash={}
        queue=[(0, start)]  
        while queue:
            c, v=heapq.heappop(queue)
            if v in hash:
                continue
            hash[v]=1
            costs[v]=c
            for node, cost in edge[v]:
                if node in hash:
                    continue
                heapq.heappush(queue, (c + cost, node))

        return costs
    N = I()
    
    edge = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b, c = MI_()
        c+=1
        edge[a].append((b, c))
        edge[b].append((a,c))
    
    Q, K = MI()
    
    cost = dijkstra(K-1, edge)
    for _ in range(Q):
        x, y = MI_()
        print(cost[x]+cost[y])

    
    
    
    
if __name__ == '__main__':
    main()

Solution (Python):
import sys

sys.setrecursionlimit(1000000)


def dfs(v, parent, adj, dist):
    for tail, weight in adj[v]:
        if tail == parent:
            continue
        dist[tail] = dist[v] + weight
        dfs(tail, v, adj, dist)


def main():
    n = int(input())
    adj = [[] for i in range(n + 1)]
    for i in range(n - 1):
        a, b, c = [int(x) for x in input().split()]
        adj[a].append((b, c))
        adj[b].append((a, c))
    q, k = [int(x) for x in input().split()]
    dist = [0] * (n + 1)
    dfs(k, k, adj, dist)
    for j in range(q):
        l, r = [int(x) for x in input().split()]
        print(dist[l] + dist[r])


main()

Solution (Python):











import sys
import heapq
input=sys.stdin.readline
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [input() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')


def main():
    
    def dijkstra(start, edge):
        costs=[inf]*N
        costs[start]=0
        hash={}
        queue=[(0, start)]  
        while queue:
            c, v=heapq.heappop(queue)
            if v in hash:
                continue
            hash[v]=1
            costs[v]=c
            for node, cost in edge[v]:
                if node in hash:
                    continue
                heapq.heappush(queue, (c + cost, node))

        return costs
    N = I()
    
    edge = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b, c = MI_()
        c+=1
        edge[a].append((b, c))
        edge[b].append((a,c))
    
    Q, K = MI()
    
    cost = dijkstra(K-1, edge)
    for _ in range(Q):
        x, y = MI_()
        print(cost[x]+cost[y])

    
    
    
    
if __name__ == '__main__':
    main()

Solution (Python):
import sys
import collections

n = int(input())
adj = [[] for i in range(n + 1)]
for i in range(n - 1):
    a, b, c = [int(x) for x in input().split()]
    adj[a].append((b, c))
    adj[b].append((a, c))
q, k = [int(x) for x in input().split()]
dist = [0] * (n + 1)
queue = collections.deque()
queue.append(k)
while len(queue) > 0:
    u = queue.popleft()
    for v, weight in adj[u]:
        if dist[v] == 0:
            queue.append(v)
            dist[v] = dist[u] + weight
for j in range(q):
    l, r = [int(x) for x in input().split()]
    print(dist[l] + dist[r])

Solution (Python):
N = int(input())

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

Q,K = list(map(int,input().split()))
q = []
for i in range(Q):
    x,y=list(map(int,input().split()))
    x=x-1
    y=y-1
    q.append([x,y])

vi = K-1 
from collections import deque
Q = deque([vi])
checked_list = [False for i in range(N)]
checked_list[vi]=True
min_path_list = [10**27 for i in range(N)] 
min_path_list[vi] = 0
while len(Q)>0:
    v = Q.pop()
    for e in e_list[v]:
        v1,c=e
        if not checked_list[v1]:
            checked_list[v1]=True
            Q.append(v1)
            min_path_list[v1]=min(min_path_list[v1],min_path_list[v]+c) 

for a in q:
    x,y=a
    print(min_path_list[x]+min_path_list[y])

Solution (Python):
import sys

sys.setrecursionlimit(100000)
INF = float('inf')

N = int(sys.stdin.readline())
ABC = [list(map(int, sys.stdin.readline().split())) for _ in range(N - 1)]
Q, K = list(map(int, sys.stdin.readline().split()))
X, Y = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(Q)]))


graph = [[] for _ in range(N + 1)]
for a, b, c in ABC:
    graph[a].append((b, c))
    graph[b].append((a, c))

stack = [(K, 0)]
dists = {K: 0}
while stack:
    v, vw = stack.pop()
    for u, w in graph[v]:
        if u not in dists:
            dists[u] = vw + w
            stack.append((u, vw + w))

for x, y in zip(X, Y):
    print(int(dists[x] + dists[y]))

Solution (Python):
import heapq
import sys

sys.setrecursionlimit(10000)
INF = float('inf')

N = int(sys.stdin.readline())
ABC = [list(map(int, sys.stdin.readline().split())) for _ in range(N - 1)]
Q, K = list(map(int, sys.stdin.readline().split()))
X, Y = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(Q)]))


def dijkstra(graph, start):
    """
    TODO: start していしなかったときに全部の距離を知りたい

    マイナスの辺があっちゃダメ
    scipy.sparse.csgraph.dijkstra は内部で使われてるフィボナッチヒープが一部のケースでめっちゃ遅いのであんまり使わないほうがよさげ
    https://atcoder.jp/contests/soundhound2018-summer-qual/submissions/5311823

    :param list of (list of (int, int)) graph:
        graph[from_index]: (to_index, weight)
    :param int start:
    :return:
    """
    dist = [float('inf') for _ in range(len(graph))]
    dist[start] = 0
    heap = []
    heapq.heappush(heap, (0, start))

    while len(heap) > 0:
        w, v = heapq.heappop(heap)
        if w > dist[v]:
            continue
        for u, dw in graph[v]:
            if w + dw < dist[u]:
                dist[u] = w + dw
                heapq.heappush(heap, (w + dw, u))
    return dist



graph = [[] for _ in range(N + 1)]
for a, b, c in ABC:
    graph[a].append((b, c))
    graph[b].append((a, c))

dists = dijkstra(graph, K)

for x, y in zip(X, Y):
    print(int(dists[x] + dists[y]))

Solution (Python):
n=int(input())
inputs=[]
for i in range(n-1):
    inputs.append([int(j) for j in input().split()])
q,k= map(int,input().split())
from collections import defaultdict
from heapq import heappop, heappush


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()
class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        
        
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        
        self.prev = defaultdict(lambda: None)

        
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]
        

g = Graph()
for src, dst, weight in inputs:
    g.add_edge(src, dst, weight)
    g.add_edge(dst, src, weight)

d = Dijkstra(g, k)   

ans=[]
for i in range(q):
    a=[int(j) for j in input().split()]
    ans.append(d.shortest_distance(a[0])+d.shortest_distance(a[1]))

for i in ans:
    print(i)

Solution (Python):
import sys
import collections
input = sys.stdin.readline
N = int(input())
tree = [[] for _ in range(N+1)]
tree_cost = [1000000001 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())

queue = collections.deque()
queue.append([K, 0])
tree_cost[K] = 0
while len(queue) > 0:
    now = queue.popleft()
    for next in tree[now[0]]:
        if tree_cost[next[0]] == 1000000001:
            queue.append(next)
            tree_cost[next[0]] = tree_cost[now[0]] + next[1]

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

Solution (Python):
import sys
import collections
input = sys.stdin.readline
N = int(input())
tree = [[] for _ in range(N+1)]
tree_cost = [1000000001 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())

queue = collections.deque()
queue.append([K, 0])
tree_cost[K] = 0
while len(queue) > 0:
    now = queue.popleft()
    for next in tree[now[0]]:
        if tree_cost[next[0]] == 1000000001:
            queue.append(next)
            tree_cost[next[0]] = tree_cost[now[0]] + next[1]

for _ in range(Q):
    x, y = map(int, input().split())
    print(tree_cost[x]+tree_cost[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())
    a,b=a-1,b-1
    G[a].append([b,c])
    G[b].append([a,c])
Q,K=map(int,input().split())
K-=1
INF=float("inf")
D=[INF for i in range(N)]
D[K]=0
stack=[(K,g[0],g[1]) for g in G[K]]
while(stack):
    a,b,c=stack.pop()
    if D[b]!=INF:
        continue
    D[b]=D[a]+c
    stack.extend([(b,g[0],g[1]) for g in G[b]])
for i in range(Q):
    x,y=map(int,input().split())
    x,y=x-1,y-1
    print(D[x]+D[y])

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

from collections import deque



Q, K = map(int,input().split())
dist_from_K = [0]*N
used = [False] * N
used[K-1] = True
before = K-1

q = deque([K-1])
while len(q) > 0:
    a = q.popleft()
    Vs = G[a]
    for u, w in Vs:
        if not used[u]:
            q.append(u)
            dist_from_K[u] = dist_from_K[a] + w
            used[u] = True

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

Solution (Python):
N=int(input())
edge=[list(map(int,input().split())) for i in range(N-1)]
inf=10**15
c=[[] for i in range(N)]
for i,j,w in edge:
    c[i-1].append((j-1,w))
    c[j-1].append((i-1,w))
Q,K=map(int, input().split())
d=[inf]*N
d[K-1]=0
v=[0]*N
import sys
sys.setrecursionlimit(10**5+9)
def dfs(p,v,d):
    for n,w in c[p]:
        if v[n]==0:
            d[n]=min(d[n],d[p]+w)
            v[n]=1
            dfs(n,v,d)
dfs(K-1,v,d)
xy=[list(map(int,input().split())) for i in range(Q)]
for x,y in xy:
    print(d[x-1]+d[y-1])

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
n = int(input())
data = [[] for i in range(n)]
for i in range(n-1):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    data[a].append([b,c])
    data[b].append([a,c])

dist = [-1 for i in range(n)]
q,k = map(int,input().split())
k -= 1
dist[k] = 0

def dfs(now,pre,d):
    dist[now] = d
    for p,q in data[now]:
        if p == pre:
            continue
        dfs(p,now,d+q)

dfs(k,-1,0)

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

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
n = int(input())
data = [[] for i in range(n)]
for i in range(n-1):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    data[a].append([b,c])
    data[b].append([a,c])

dist = [-1 for i in range(n)]
q,k = map(int,input().split())
k -= 1
dist[k] = 0

def dfs(now,pre,d):
    dist[now] = d
    for p,q in data[now]:
        if p == pre:
            continue
        dfs(p,now,d+q)

dfs(k,-1,0)

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

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
n = int(input())
data = [[] for i in range(n)]
for i in range(n-1):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    data[a].append([b,c])
    data[b].append([a,c])

dist = [-1 for i in range(n)]
q,k = map(int,input().split())
k -= 1
dist[k] = 0

def dfs(now,pre,d):
    dist[now] = d
    for p,q in data[now]:
        if p == pre:
            continue
        dfs(p,now,d+q)

dfs(k,-1,0)

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

Solution (Python):
n=int(input())
r=[[] for i in range(n+1)]
for i in range(n-1):
    a,b,c=map(int,input().split())
    r[a].append((b,c))
    r[b].append((a,c))
ans=[-1 for i in range(n+1)]
Q,k=map(int,input().split())
q=[(k,0)]
while len(q)>0:
    v,l=q.pop()
    ans[v]=l
    for V,L in r[v]:
        if(ans[V]==-1):
            q.append((V,l+L))
for i in range(Q):
    x,y=map(int,input().split())
    print(ans[x]+ans[y])

Solution (Python):
import heapq
def dijkstra(v,s,path):
    inf = float('inf')

    
    d = [inf for i in range(v)]
    d[s] = 0

    
    q = [[0,s]]
    heapq.heapify(q)

    
    
    while q:
        p = heapq.heappop(q)

        
        if d[p[1]]<p[0]:
            continue

        
        for i in range(len(path[p[1]])):
            
            if d[path[p[1]][i][1]] > d[p[1]] + path[p[1]][i][0]:
                d[path[p[1]][i][1]] = d[p[1]]+path[p[1]][i][0]
                heapq.heappush(q,[d[path[p[1]][i][1]], path[p[1]][i][1]])
    return d


n = int(input())
p = [[] for i in range(n)]

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

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

d = dijkstra(n,k,p)

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

Solution (Python):
from heapq import heappop, heappush


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


INF = float('inf')
N = int(input())
g = {i: []for i in range(N)}
for i in range(N - 1):
    a, b, c = map(int, input().split())
    g[a - 1].append(edge(b - 1, c))
    g[b - 1].append(edge(a - 1, c))
Q, K = map(int, input().split())
dist = {i: INF for i in range(N)}
dist[K - 1] = 0
hq = [(0, K - 1)]
done = [0] * N
done[K - 1] = 1
while hq:
    d, n = heappop(hq)
    dist[n] = d
    for eg in g[n]:
        if done[eg.to] == 0:
            heappush(hq, (d + eg.cost, eg.to))
            done[eg.to] = 1
for i in range(Q):
    x, y = map(int, input().split())
    print(dist[x - 1] + dist[y - 1])