Problem:


Score : 400 points

Problem Statement

You are given a tree with N vertices.

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

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

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

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

Constraints

3≤N≤10^5 

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

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

The given graph is a tree.

1≤Q≤10^5 

1≤K≤N 

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

x_j≠y_j (1≤j≤Q) 

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

Input

Input is given from Standard Input in the following format:  

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

Output

Print the responses to the queries in Q lines.

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

Sample Input 1

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

Sample Output 1

3
2
4

The shortest paths for the three queries are as follows:

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

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

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

Sample Input 2

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

Sample Output 2

5
14
22

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

Sample Input 3

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

Sample Output 3

17000000000



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


Sample output:
3
2
4

Submission status: Accepted

Solution code:
import sys
# sys.setrecursionlimit(100000)
from collections import defaultdict
from heapq import heappop, heappush


class Dijkstra:
    """Graph input:
    {
    node:{node:cost,node:cost...},
    node:{node:cost,node:cost...},
    ...
    }
    """

    def __init__(self, graph: dict, N: int):
        self.graph = graph
        self.costs = [float("inf")] * N

    def calculate(self, start):
        queue = list()

        # step1: push the start point into the priority queue
        self.costs[start] = 0
        heappush(queue, (0, start))  # (cost,node)

        while queue:
            # step2: get the minimum cost node from unfixed node and fix the cost
            cost_from_start, min_node = heappop(queue)

            # step3: update the direct connected nodes
            for link, cost in self.graph[min_node].items():
                if cost_from_start + cost < self.costs[link]:
                    self.costs[link] = cost_from_start + cost
                    heappush(queue, (self.costs[link], link))

        return self.costs


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


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    n = input_int()
    graph = defaultdict(dict)
    for _ in range(n - 1):
        a, b, c = input_int_list()
        graph[a][b] = c
        graph[b][a] = c
    # dp = warshall_floyd(graph, n + 1) O(n**3) => TLD

    q, k = input_int_list()

    solver = Dijkstra(graph, n + 1)
    costs = solver.calculate(k)

    ans = []
    for _ in range(q):
        x, y = input_int_list()
        ans.append(costs[x] + costs[y])
    for i in ans:
        print(i)

    return


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    G = {}
    for i in range(n):
        G[i+1] = []
    for _ in range(n-1):
        a,b,c = map(int,input().split())
        G[a] += [[b,c]]
        G[b] += [[a,c]]
    q,k = map(int,input().split())
    dist = [-1]*n
    dist[k-1] = 0
    que = [k]
    while len(que) > 0:
        s = que.pop(0)
        for [nv,c] in G[s]:
            if dist[nv-1] != -1:
                continue
            dist[nv-1] = dist[s-1]+c
            que.append(nv)
    for _ in range(q):
        x,y = map(int,input().split())
        print(dist[x-1]+dist[y-1])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def ij2str(i, j):
    return str(i) + '+' + str(j)

n = int(input())
tree = [[] for _ in range(n)]
dis = [0 for _ in range(n)]
c_list = {}
visited = set()
for i in range(n-1):
    a, b, c = map(int, input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
    c_list[ij2str(a-1, b-1)] = c
    c_list[ij2str(b-1, a-1)] = c

from collections import deque

q, k = map(int, input().split())
visited.add(k-1)
next = deque()
next.append(k-1)

while len(next):
    i = next.popleft()
    for j in tree[i]:
        if not j in visited:
            dis[j] = dis[i] + c_list[ij2str(i, j)]
            next.append(j)
            visited.add(j)

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

Submission status: Accepted

Solution code:
from collections import deque


def nearlist(N, LIST):  # 隣接リスト
    NEAR = [{} for _ in range(N)]
    for a, b, c in LIST:
        NEAR[a - 1][b - 1] = c
        NEAR[b - 1][a - 1] = c
    return NEAR


def bfs(NEAR, S, N):  # 幅優先探索  # キュー
    DIST = [-1 for _ in range(N)]  # 前処理
    DIST[S] = 0
    que, frag = deque([S]), set([S])

    while que:
        q = que.popleft()
        for i, c in NEAR[q].items():  # 移動先の候補
            if i in frag:  # 処理済みか否か
                continue
            DIST[i] = DIST[q] + c
            que.append(i), frag.add(i)
    return DIST


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

near = nearlist(n, abc)
dist = bfs(near, k - 1, n)
for x, y in xy:
    print(dist[x - 1] + dist[y - 1])

Submission status: Accepted

Solution code:
def nearlist(N, LIST):  # 隣接リスト
    NEAR = [{} for _ in range(N)]
    for a, b, c in LIST:
        NEAR[a - 1][b - 1] = c
        NEAR[b - 1][a - 1] = c
    return NEAR


def dfs(NEAR, S, N):  # 深優先探索  # スタック
    DIST = [-1 for _ in range(N)]  # 前処理
    DIST[S] = 0
    stack, frag = [S], set([S])

    while len(stack) > 0:
        q = stack.pop()
        for i, c in NEAR[q].items():  # 移動先の候補
            if i in frag:  # 処理済みか否か
                continue
            DIST[i] = DIST[q] + c
            stack.append(i), frag.add(i)
    return DIST


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

near = nearlist(n, abc)
dist = dfs(near, k - 1, n)
for x, y in xy:
    print(dist[x - 1] + dist[y - 1])

Submission status: Accepted

Solution code:
from collections import deque


def nearlist(N, LIST):  # 隣接リスト
    NEAR = [{} for _ in range(N)]
    for a, b, c in LIST:
        NEAR[a - 1][b - 1] = c
        NEAR[b - 1][a - 1] = c
    return NEAR


def dfs(NEAR, S, N):  # 深優先探索  # スタック
    DIST = [-1 for _ in range(N)]  # 前処理
    DIST[S] = 0
    stack, frag = [S], set([S])

    while len(stack) > 0:
        q = stack.pop()
        for i, c in NEAR[q].items():  # 移動先の候補
            if i in frag:  # 処理済みか否か
                continue
            DIST[i] = DIST[q] + c
            stack.append(i), frag.add(i)
    return DIST


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

near = nearlist(n, abc)
dist = dfs(near, k - 1, n)
for x, y in xy:
    print(dist[x - 1] + dist[y - 1])

Submission status: Accepted

Solution code:
from collections import deque


def nearlist(N, LIST):  # 隣接リスト
    NEAR = [{} for _ in range(N)]
    for a, b, c in LIST:
        NEAR[a - 1][b - 1] = c
        NEAR[b - 1][a - 1] = c
    return NEAR


def bfs(NEAR, S, N):  # 幅優先探索  # キュー
    DIST = [-1 for _ in range(N)]  # 前処理
    DIST[S] = 0
    que, frag = deque([S]), set([S])

    while len(que) > 0:
        q = que.popleft()
        for i, c in NEAR[q].items():  # 移動先の候補
            if i in frag:  # 処理済みか否か
                continue
            DIST[i] = DIST[q] + c
            que.append(i), frag.add(i)
    return DIST


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

near = nearlist(n, abc)
dist = bfs(near, k - 1, n)
for x, y in xy:
    print(dist[x - 1] + dist[y - 1])

Submission status: Accepted

Solution code:
import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

itta=[0]*(n+1)
dic=defaultdict(list)
for a,b,c in abc:
    dic[a].append((b,c))
    dic[b].append((a,c))

d=deque([(k,0)])
while d:
    now=d.popleft()
    if itta[now[0]]!=0:
        continue
    itta[now[0]]=now[1]
    for i,j in dic[now[0]]:
        d.append((i,j+now[1]))
# print(itta)
itta[k]=0
for x,y in xy:
    print(itta[x]+itta[y])

Submission status: Accepted

Solution code:
from collections import deque


def nearlist(N, LIST):  # 隣接リスト
    NEAR = [set() for _ in range(N)]
    COST = {}
    for a, b, c in LIST:
        NEAR[a - 1].add(b - 1)
        NEAR[b - 1].add(a - 1)
        COST[(a - 1, b - 1)] = c
        COST[(b - 1, a - 1)] = c
    return NEAR, COST


def bfs(NEAR, S, N):  # 幅優先探索  # キュー
    DIST = [-1 for _ in range(N)]  # 前処理
    DIST[S] = 0
    que, frag = deque([S]), set([S])

    while len(que) > 0:
        q = que.popleft()
        for i in NEAR[q]:  # 移動先の候補
            if i in frag:  # 処理済みか否か
                continue
            DIST[i] = DIST[q] + cost[(q, i)]
            que.append(i), frag.add(i)
    return DIST


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

near, cost = nearlist(n, abc)
dist = bfs(near, k - 1, n)
for x, y in xy:
    print(dist[x - 1] + dist[y - 1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
n = int(input())
t = [[] for _ in range(n)]
for i in range(n-1):
  a,b,c = map(int,input().split())
  t[a-1].append((b-1,c))
  t[b-1].append((a-1,c))
q,k = map(int,input().split())
k -= 1
l = [0]*n
def dfs(a,b,c):
  for i,j in t[b]:
    if i != a:
      l[i] = c+j
      dfs(b,i,c+j)
dfs(-1,k,0)
for _ in range(q):
  x,y = map(lambda x:int(x)-1,input().split())
  print(l[x]+l[y])

Submission status: Accepted

Solution code:
import heapq as hq
N = int(input())
edges = [[] for _ in range(N)]
for _ in range(N-1):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    edges[a].append((b, c))
    edges[b].append((a, c))
Q, K = map(int,input().split())
INF = float("inf")
d = [INF]*N
K -= 1
d[K] = 0
q = [(0,K)]
while q:
    dist, i = hq.heappop(q)
    if d[i] < dist:
        continue
    for j, w in edges[i]:
        if d[j] > d[i]+w:
            d[j] = d[i]+w
            hq.heappush(q, (d[j], j))
for _ in range(Q):
    x, y = map(int,input().split())
    x -= 1
    y -= 1
    print(d[x]+d[y])

Submission status: Accepted

Solution code:
from collections import deque

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

graph = [[] for i in range(N+1)]
for i,j,k in abc:
    graph[i].append((j,k))
    graph[j].append((i,k))
    
r = [-1 for i in range(N+1)] 
Q = deque()
Q.append(K)
r[K] = 0

while Q:
    x = Q.popleft()
    for to, dis in graph[x]:
        if r[to] == -1:
            r[to] = r[x] + dis
            Q.append(to)
            
for _ in range(q):
    x, y = map(int, input().split())
    print(r[x] + r[y])

Submission status: Accepted

Solution code:
from sys import stdin

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

n = int(input())
edge = [[] for _ in range(n)]
weight = [[] for _ in range(n)]
for _ in range(n-1):
    i, j, k = map(int, input().split())
    i -= 1
    j -= 1
    edge[i].append(j)
    edge[j].append(i)
    weight[i].append(k)
    weight[j].append(k)

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

k -= 1
# root = k
# DFS
distance = [-1] * n
distance[k] = 0
todo = [k]
while len(todo) > 0:
    i = todo.pop(-1)
    for j in range(len(edge[i])):
        if distance[edge[i][j]] == -1:
            distance[edge[i][j]] = distance[i] + weight[i][j]
            todo.append(edge[i][j])

ans = []
for _ in range(q):
    i, j = map(int, input().split())
    ans.append(distance[i-1] + distance[j-1])

for i in ans:
    print(i)

Submission status: Accepted

Solution code:
from sys import stdin
from sys import stdin
def input():
    return stdin.readline().strip()

n = int(input())
edge = [[] for _ in range(n)]
weight = [[] for _ in range(n)]
for _ in range(n-1):
    i, j, k = map(int, input().split())
    i -= 1
    j -= 1
    edge[i].append(j)
    edge[j].append(i)
    weight[i].append(k)
    weight[j].append(k)

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

k -= 1
# root = k
# DFS
distance = [-1] * n
distance[k] = 0
todo = [k]
while len(todo) > 0:
    i = todo.pop(-1)
    for j in range(len(edge[i])):
        if distance[edge[i][j]] == -1:
            distance[edge[i][j]] = distance[i] + weight[i][j]
            todo.append(edge[i][j])

ans = []
for _ in range(q):
    i, j = map(int, input().split())
    ans.append(distance[i-1] + distance[j-1])

for i in ans:
    print(i)

Submission status: Accepted

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

n=int(input())

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

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

dist=[-1]*n

def dfs(now, parent, d):
    dist[now]=d
    for i in graph[now]:
        if i[0]==parent:
            continue
        else:
            dfs(i[0], now, d+i[1])

dfs(k, -1, 0)

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

Submission status: Accepted

Solution code:
from networkx import *
N = int(input())
E1 = [list(map(int,input().split())) for n in range(N-1)]
Q,K = map(int,input().split())
E2 = [list(map(int,input().split())) for q in range(Q)]
G = Graph()

for a,b,c in E1:
  G.add_edge(a-1,b-1,weight=c)

D = shortest_path_length(G,target=K-1,weight="weight")

for x,y in E2:
  print(D[x-1]+D[y-1])

Submission status: Accepted

Solution code:
from networkx import *
N = int(input())
E1 = [list(map(int,input().split())) for n in range(N-1)]
Q,K = map(int,input().split())
E2 = [list(map(int,input().split())) for q in range(Q)]
G = Graph()

for a,b,c in E1:
  G.add_edge(a-1,b-1,weight=c)

D = shortest_path_length(G,weight="weight",target=K-1)

for x,y in E2:
  print(D[x-1]+D[y-1])

Submission status: Accepted

Solution code:
from networkx import *
N = int(input())
E1 = [list(map(int,input().split())) for n in range(N-1)]
Q,K = map(int,input().split())
E2 = [list(map(int,input().split())) for q in range(Q)]
G = Graph()

for a,b,c in E1:
  G.add_edge(a-1,b-1,weight=c)

D = shortest_path_length(G,K-1,weight="weight")

for x,y in E2:
  print(D[x-1]+D[y-1])

Submission status: Accepted

Solution code:
N = int(input())
G = [[] for n in range(N)]

for n 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())
d = N*[-1]
d[K-1] = 0
q = [K-1]

while q:
  t = q.pop()
  for b,c in G[t]:
    if d[b]==-1:
      d[b] = d[t]+c
      q.append(b)

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

Submission status: Accepted

Solution code:
""" ABC070D Transit Tree Path
"""
from collections import deque
from heapq import heapify, heappop, heappush, heappushpop


class PriorityQueue:
    """
    優先度付きキューの
    """
    def __init__(self, heap):
        self.heap = heap
        heapify(self.heap)
    
    def push(self, item):
        heappush(self.heap, item)
    
    def pop(self):
        return heappop(self.heap)
    
    def pushpop(self, item):
        return heappushpop(self.heap, item)
    
    def __call__(self):
        return self.heap
    
    def __len__(self):
        return len(self.heap)


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

Q, K = map(int, input().split())
INF = float("inf")


def dijkstra(adj: list, s: int):
    Color = [0]*N # 0: 未訪問 1: Seen 2: Visited
    D = [INF]*N #始点からの距離(重み)
    P = [None]*N #親

    D[s] = 0
    P[s] = None
    PQ = PriorityQueue([(0, s)]) #(Cost, Node)を格納し、PQにする。

    while PQ: # PQに候補がある限り

        min_cost, u = PQ.pop() # 最小コストなノードu

        Color[u] = 2 # uをVisitedに。

        if D[u] < min_cost:
            # 更新の必要なし.
            continue

        for adj_idx, adj_w in adj[u]:
            if Color[adj_idx] != 2: #訪問済みでないなら
                if D[u] + adj_w < D[adj_idx]: #最小コストを更新できるなら、
                    D[adj_idx] = D[u] + adj_w
                    P[adj_idx] = u
                    # PQに(隣接要素のコスト, 隣接要素の番号)を容れる
                    PQ.push((D[adj_idx], adj_idx))
                    Color[adj_idx] = 1
    
    return D, P

D, P = dijkstra(G, s=K-1)
for q in range(Q):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    print(D[x]+D[y])

Submission status: Accepted

Solution code:
import heapq

def dijkstra(s):
	hq = [(0, s)]
	heapq.heapify(hq) # リストを優先度付きキューに変換
	cost = [float('inf')] * n # 行ったことのないところはinf
	cost[s] = 0 # 開始地点は0
	while hq:
		c, v = heapq.heappop(hq)
		if c > cost[v]: # コストが現在のコストよりも高ければスルー
			continue
		for d, u in e[v]:
			tmp = d + cost[v]
			if tmp < cost[u]:
				cost[u] = tmp
				heapq.heappush(hq, (tmp, u))
	return cost

n = int(input())
e = [[] for _ in range(n)]
for _ in range(n-1):
	a,b,c = map(int,input().split())
	a,b = a-1, b-1
	e[a].append((c, b))
	e[b].append((c, a))
q,k = map(int,input().split())
l = dijkstra(k-1)
for _ in range(q):
	x,y = map(int,input().split())
	print(l[x-1] + l[y-1])

Submission status: Accepted

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

n= int(input())
G=[[] for i in range(n+1)]

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

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


D=[None]*(n+1)
 
def dfs(x,d):
    D[x]=d
    for yy,dd in G[x] :
        if D[yy] is not None:
            continue
        dfs(yy,dd+d)
dfs(k,0)

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

Submission status: Accepted

Solution code:
import heapq

N = int(input())

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

def dijkstra(s):
  hq = [(0, s)]
  heapq.heapify(hq)
  cost = [float('inf')] * N
  cost[s] = 0
  while hq:
    c, v = heapq.heappop(hq)
    if c > cost[v]:
      continue
    for d, u in Tree[v]:
      tmp = d + cost[v]
      if tmp < cost[u]:
        cost[u] = tmp
        heapq.heappush(hq, (tmp, u))
  return cost

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

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

Submission status: Accepted

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

Q,s = map(int,input().split())
from heapq import heapify,heappush,heappop
D_INF = 10**15
d = [D_INF]*(N+1)#最速到達距離。でかい数で初期化
d[s] = 0#スタート
que = []
heapify(que)
heappush(que,(d[s],s))

while(len(que)):
    time,place = heappop(que)
    if time > d[place]:
        continue
    for i in range(0,len(adj_list[place]),1):
        if d[adj_list[place][i][0]] > time + adj_list[place][i][1]:#とりあえず円で
            d[adj_list[place][i][0]] = time + adj_list[place][i][1]
            heappush(que,(d[adj_list[place][i][0]],adj_list[place][i][0]))


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

for i in range(len(ans)):
    print(ans[i])

Submission status: Accepted

Solution code:
from collections import deque

N=int(input())

E={i:{} for i in range(1,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())
inf=float("inf")
Dist=[inf]*(N+1)
Dist[K]=0
X=deque([K])

while X:
    u=X.popleft()
    for v in E[u]:
        if Dist[v]==inf:
            X.append(v)
            Dist[v]=Dist[u]+E[u][v]

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

print("\n".join(map(str,T)))

Submission status: Accepted

Solution code:
import sys
mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict #すべてのkeyが用意されてる defaultdict(int)で初期化
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
from bisect import bisect_left as bileft, bisect_right as biright
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########

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

queue= deque([ [k,l[0],l[1]] for l in G[k] ] )
# print(queue)
dist=[-1]*n ; dist[k]=0
while queue:
    pre, now, kati = queue.pop()
    # print(pre,now)
    dist[now]= dist[pre]+kati
    for to,katin in G[now]:
        if to!= pre:
            queue.appendleft([now,to,katin ])

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

Submission status: Accepted

Solution code:
n = int(input())
g = [[] for i in range(n)]
for i in range(n-1):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    g[a].append((b,c))
    g[b].append((a,c))
q,k = map(int,input().split())
k -= 1
c = [-1]*n
c[k] = 0
stack = [k]
while stack:
    cur = stack.pop()
    for next_,cost in g[cur]:
        if c[next_]<0:
            c[next_] = c[cur]+cost
            stack.append(next_)

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

Submission status: Accepted

Solution code:
from collections import deque

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

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

d = [-1] * n
d[k] = 0
q = deque()
q.append([k, 0])
while q:
    f, cc = q.pop()
    for t, nc in e[f]:
        if d[t] == -1:
            d[t] = cc + nc
            q.append([t, d[t]])

for i in range(m):
    f, t = map(int,input().split())
    f -= 1
    t -= 1
    print(d[f] + d[t])

Submission status: Accepted

Solution code:
N =int(input())
#graph作成
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())
K -= 1
query = [tuple(int(x) for x in input().split()) for _ in range(Q)]

        
seen = {K} 
v = [K]
distfromK =[0] * N
while len(v) != 0:  #bfsでdistfromKを埋めていく
    for nv in graph[v[0]]:
        if nv[0] in seen:
            continue
        distfromK[nv[0]] = distfromK[v[0]] + nv[1]
        v.append(nv[0])
        seen.add(nv[0])
    v.pop(0)

for q in query:
    print(distfromK[q[0]-1]+distfromK[q[1]-1])

Submission status: Accepted

Solution code:

from heapq import heappop,heappush

icase=0
if icase==0:
    n=int(input())
    g=[[] for i in range(n)]
    for i in range(n-1):
        ai,bi,ci=map(int,input().split())
        g[ai-1].append((bi-1,ci))
        g[bi-1].append((ai-1,ci))
if icase==1:
    n=5
    g=[[(1, 1), (2, 1)], [(0, 1), (3, 1)], [(0, 1), (4, 1)], [(1, 1)], [(2, 1)]]
if icase==2:
    n=7
    g=[[(1, 1), (2, 3), (3, 5), (4, 7), (5, 9), (6, 11)], [(0, 1)], [(0, 3)], [(0, 5)], [(0, 7)], [(0, 9)], [(0, 11)]]

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

hq=[]
heappush(hq,(0,k)) 

inf=float("INF")
dist=[inf]*n
dist[k]=0
while len(hq)>0:
    dd,state = heappop(hq)
#    print("dd:",dd,"state:",state,"q:",q)
    for v,dv in g[state]:
#        print("v:",v,"dv:",dv,"g[state]:",g[state],"parent[v]:",parent[v])
        if dist[v]>dist[state]+dv:
            dist[v]=dist[state]+dv
            heappush(hq,(dist[v],v))
#            print(" state:",state,"v:",v,"dist[v]",dist[v])

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

Submission status: Accepted

Solution code:
import heapq
import sys

input = sys.stdin.readline

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

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



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import queue

n=int(input())

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

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

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

xy=[]

for i in range(q):
  xy.append(list(map(int,input().split())))


distance=[0 for i in range(n)]
seen=[0 for i in range(n)]

que=queue.Queue()

que.put(k)
seen[k-1]=1

while not que.empty():
  c=que.get()
  for aa,cc in clis[c-1]:
    if seen[aa-1]==0:
      distance[aa-1]=distance[c-1]+cc
      seen[aa-1]=1
      que.put(aa)

for i in range(q):
  print(distance[xy[i][0]-1]+distance[xy[i][1]-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())
def NIJIGEN(H): return [list(input()) for i in range(H)]
def bfs(place,dis):
  for i in tree[place]:
    a,b=i
    if a not in finish:
      finish.add(a)
      disli[a]=dis+b
      bfs(a,dis+b)
N=INT()
tree=[[] for _ in range(N)]
for i in range(N-1):
  a,b,c=MAP()
  tree[a-1].append([b-1,c])
  tree[b-1].append([a-1,c])
Q,K=MAP()#処理
disli=[0 for i in range(N)]
finish=set([K-1])
bfs(K-1,0)
for i in range(Q):
  a,b=MAP()
  print(disli[a-1]+disli[b-1])

Submission status: Accepted

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

q, k = map(int, input().split())
k -= 1
d = deque([k])
visited = [False]*n
visited[k] = True
distance_from_k = [0]*n
while d:
    p = d.popleft()
    for child, c in edges[p]:
        if visited[child]:
            continue
        visited[child] = True
        d.append(child)
        distance_from_k[child] += distance_from_k[p] + c
#print(distance_from_k)

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

Submission status: Accepted

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())

def solve():
    N = INT()
    adj = [[] for _ in range(N)]
    for i in range(N-1):
        a, b, c = MAP()
        adj[a-1].append([b-1, c])
        adj[b-1].append([a-1, c])

    Q, K = MAP()
    K -= 1

    def dijkstra(K, adj):
        #K: 始点, adj[point, cost]:隣接リスト
        d = [inf]*N
        d[K] = 0
        que = []
        heappush(que, K)

        while que:
            v = heappop(que)
            for b, c in adj[v]:
                if d[b] > d[v] + c:
                    d[b] = d[v] + c
                    heappush(que, b)
        return d

    d = dijkstra(K, adj)
    for i in range(Q):
        x, y = MAP()
        print(d[x-1]+d[y-1])

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())

def solve():
    N = INT()
    adj = [[] for _ in range(N)]
    for i in range(N-1):
        a, b, c = MAP()
        adj[a-1].append([b-1, c])
        adj[b-1].append([a-1, c])

    Q, K = MAP()
    K -= 1

    d = [inf]*N
    d[K] = 0
    que = []
    heappush(que, K)

    while que:
        v = heappop(que)
        for b, c in adj[v]:
            if d[b] > d[v] + c:
                d[b] = d[v] + c
                heappush(que, b)

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

if __name__ == '__main__':
    solve()