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:
from sys import stdin
from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)
N = int(stdin.readline().rstrip())
adj = defaultdict(set)

for i in range(N-1):
    a,b,c = [int(x) for x in stdin.readline().rstrip().split()]
    adj[a].add((b,c))
    adj[b].add((a,c))
    
Q,K = [int(x) for x in stdin.readline().rstrip().split()]

visited = [False]*(N+1)
dist = [0]*(N+1)

def dfs(i,j):
    if visited[i]:
        return
    dist[i] = j
    visited[i] = True
    
    for node,d in adj[i]:
        dfs(node,d+j)
        
dfs(K,0)

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N=int(input())
    edge=[[] for _ in range(N)]
    for _ in range(N-1):
        a,b,c=map(int1,input().split())
        c+=1
        edge[a].append((c,b))
        edge[b].append((c,a))
    
    Q,K=map(int,input().split())
    K-=1
    from heapq import heappop,heappush
    def dijkstra(start,n,edges):
        d=[INF]*n
        used=[False]*n
        d[start]=0
        used[start]=True
        edgelist=[]
        for edge in edges[start]:
            heappush(edgelist,edge)
        while edgelist:
            minedge=heappop(edgelist)
            if used[minedge[1]]:
                continue
            v=minedge[1]
            d[v]=minedge[0]
            used[v]=True
            for edge in edges[v]:
                if not used[edge[1]]:
                    heappush(edgelist,(edge[0]+d[v],edge[1]))
        return d
    
    d=dijkstra(K,N,edge)
    for _ in range(Q):
        x,y=map(int1,input().split())
        print(d[x]+d[y])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from queue import deque

n = int(input())
li = [[] for _ in range(n)]
length = {}
length_path = [0]*n

for i in range(n-1):
    u,v,w = map(int,input().split())
    u,v = u-1,v-1
    if u < v:
        length[(u,v)] = w
    else:
        length[(v,u)] = w
    li[u].append(v)
    li[v].append(u)

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

work_queue = deque([])
visited = [False]*n

work_queue.append(k)

while work_queue:
    now = work_queue.popleft()
    visited[now] = True
    for i in li[now]:
        if visited[i]:
            continue
        work_queue.append(i)
        visited[i] = True
        if now < i:
            length_path[i] = length_path[now]+length[(now,i)]
        else:
            length_path[i] = length_path[now]+length[(i,now)]

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

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
n=int(input())
edges=[[] for i in range(n)]
dis=[-1]*n
for _ in range(n-1):
  a,s,d=map(int,input().split())
  a-=1;s-=1
  edges[a].append((s,d))
  edges[s].append((a,d))
q,k=map(int,input().split())
dis[k-1]=0
def dfs(now):
  for i,d in edges[now]:
    if dis[i]==-1:
      dis[i]=dis[now]+d
      dfs(i)
dfs(k-1)
for _ in range(q):
  a,s=map(int,input().split())
  print(dis[a-1]+dis[s-1])

Submission status: Accepted

Solution code:
import sys
import heapq

input = sys.stdin.readline


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

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

    dist = [None] * N
    h = [(0, K, -1)]
    while h:
        d0, node, parent = heapq.heappop(h)
        dist[node] = d0
        for d1, child in nb[node]:
            if child != parent:
                heapq.heappush(h, (d0 + d1, child, node))

    for i in range(Q):
        x, y = map(int, input().split())
        # print(f"{x}->K = {dist[x]}, K->{y} = {dist[y]}")
        print(dist[x - 1] + dist[y - 1])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import heapq

input = sys.stdin.readline


def main():

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

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

    dist = [2 ** 62] * N
    h = [(0, K, -1)]
    while h:
        d0, node, parent = heapq.heappop(h)
        if d0 >= dist[node]:
            continue
        dist[node] = d0
        for d1, child in nb[node]:
            if child != parent and d0 + d1 < dist[child]:
                heapq.heappush(h, (d0 + d1, child, node))

    for i in range(Q):
        x, y = map(int, input().split())
        # print(f"{x}->K = {dist[x]}, K->{y} = {dist[y]}")
        print(dist[x - 1] + dist[y - 1])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# solution

data=int(input())

abc=[list(map(int,input().split())) for _ in [0]*(data-1)]

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

array1=[list(map(int,input().split())) for _ in [0]*q]

k-=1

tree=[[] for _ in [0]*data]

dist=[-1]*data

dist[k]=0

[tree[a-1].append([b-1,c]) for a,b,c in abc]

[tree[b-1].append([a-1,c]) for a,b,c in abc]

q=[k]

while(q):
	qq=[]
	for i in q:
		for j,k in tree[i]:
			if dist[j]<0:
				dist[j]=dist[i]+k
				qq.append(j)
	q=qq

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

Submission status: Accepted

Solution code:
# solution

data=int(input())

abc=[list(map(int,input().split())) for _ in [0]*(data-1)]

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

array1=[list(map(int,input().split())) for _ in [0]*q]

k-=1

tree=[[] for _ in [0]*data]

dist=[-1]*data

dist[k]=0

[tree[a-1].append([b-1,c]) for a,b,c in abc]

[tree[b-1].append([a-1,c]) for a,b,c in abc]

q=[k]

while(q):
	qq=[]
	for i in q:
		for j,k in tree[i]:
			if dist[j]<0:
				dist[j]=dist[i]+k
				qq.append(j)
	q=qq

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

Submission status: Accepted

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

def distance(k):
    seen = set()
    dis_l = {}
    d = 0
    stack = deque([[tree[k], d]])
    flag = True
    while stack:
        connect, d = stack.popleft()
        for i in connect:
            if i[0] not in seen:
                seen.add(i[0])
                d += i[1]
                dis_l[i[0]] = d
                stack.append([tree[i[0]], d])
                d -= i[1]
    return dis_l

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

Submission status: Accepted

Solution code:
n = int(input())
abc = [list(map(int, input().split())) for i in range(n-1)]
q,k = map(int, input().split())
tree = [list() for i in range(n+1)]
visited = [0] * (n+1)
dist = [0] * (n+1)
for a,b,c in abc:
  tree[a].append((b,c))
  tree[b].append((a,c))
stack = [k]
visited[k] = 1
while stack:
  now = stack.pop()
  for NEXT,d in tree[now]:
    if not visited[NEXT]:
      visited[NEXT] = 1
      dist[NEXT] = dist[now] + d
      stack.append(NEXT)
for i in range(q):
  x,y = map(int, input().split())
  print(dist[x]+dist[y])

Submission status: Accepted

Solution code:
import heapq


def dijkstra(start, n_nodes, edges):
    dist = [float("inf")] * n_nodes
    dist[start] = 0
    q = [(dist[start], start)]
    heapq.heapify(q)

    while q:
        d, i = heapq.heappop(q)
        if d > dist[i]:
            continue

        for w, j in edges[i]:
            if d + w < dist[j]:
                dist[j] = d + w
                heapq.heappush(q, (dist[j], j))

    return dist


def main():
    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((c, b))
        edges[b].append((c, a))

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


main()

Submission status: Accepted

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

abc = [[] for i in range(n+1)]

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

Q,k = map(int,input().split())
xy = [[int(i) for i in input().split()] for j in range(Q)]

q = queue.Queue()

q.put(k)

path = [-1]*(n+1)
path[k] = 0

while not q.empty():
    tmp = q.get()
    for i in range(len(abc[tmp])):
        #print(abc[tmp])
        #exit()
        num = abc[tmp][i][0]
        if path[num] != -1:
            continue
        else:
            path[num] = path[tmp] + abc[tmp][i][1]
            q.put(num)
            
for i in range(Q):
    print(path[xy[i][0]]+path[xy[i][1]])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500000)
 
N = int(input())
ABC = [list(map(int, input().split())) for i in range(N-1)]
Q, K = map(int, input().split())
D = [0] * (N+1)
L = [[] for i in range(N+1)]
for a, b, c in ABC:
    L[a].append([b, c])
    L[b].append([a, c])
 
 
def dfs(n, np):
    for nc in L[n]:
        if nc[0] == np:
            continue
        else:
            D[nc[0]] = D[n] + nc[1]
            dfs(nc[0], n)
 
 
dfs(K, 0)
for i in range(Q):
    x, y = map(int, input().split())
    print(D[x] + D[y])

Submission status: Accepted

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

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


def dfs(s):
    d = [-1] * n
    d[s] = 0
    stack = [s]

    while stack:
        u = stack.pop()
        for v, c in adj[u]:
            if d[v] == -1:
                d[v] = d[u] + c
                stack.append(v)

    return d


d = dfs(k - 1)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500000)
 
N = int(input())
ABC = [list(map(int, input().split())) for i in range(N-1)]
Q, K = map(int, input().split())
D = [0] * (N+1)
L = [[] for i in range(N+1)]
for a, b, c in ABC:
    L[a].append([b, c])
    L[b].append([a, c])
 
 
def dfs(n, np):
    for nc in L[n]:
        if nc[0] == np:
            continue
        else:
            D[nc[0]] = D[n] + nc[1]
            dfs(nc[0], n)
 
 
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 sys
sys.setrecursionlimit(10**7)


def dfs(start, dist, distance_list, explored):
    for node, cost in tree[start]:
        if explored[node] is False:
            explored[node] = True
            distance_list[node] = dist + cost
            dfs(node, distance_list[node], distance_list, explored)
    return distance_list


n = int(input())
tree = [[] for _ in range(n)]
distance = [float('inf') for _ in range(n)]

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

q, k = map(int, input().split())
k -= 1
query = []
distance[k] = 0

for _ in range(q):
    x, y = map(int, input().split())
    query.append((x-1, y-1))

XX = [False for _ in range(n)]
XX[k] = True

X = dfs(k, 0, distance, explored=XX)

for i, j in query:
    print(X[i] + X[j])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(20000000)
from collections import defaultdict
n = int(input())

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

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

# k からの距離を求める
dist = [-1 for _ in range(n+1)]
is_checked = [False for _ in range(n+1)]
def dfs(num, cur_dist):
    global dist, is_checked
    for next_num, d in edges[num]:
        if not is_checked[next_num]:
            is_checked[next_num] = True
            dist[next_num] = cur_dist + d
            dfs(next_num, cur_dist + d)
dist[k] = 0
is_checked[k] = True
dfs(k, 0)

ans = []
for _ in range(q):
    x, y = map(int, input().split())
    ans.append(str(dist[x] + dist[y]))
print("\n".join(ans))

Submission status: Accepted

Solution code:
N = int(input())
import heapq
def dijkstra_heap(s):
    d = [float("inf")] * N
    used = [True] * N
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d


edge = [[] for i in range(N)]
for i in range(N-1):
    x,y,z = map(int,input().split())
    edge[x-1].append([z,y-1])
    edge[y-1].append([z,x-1])
Q, K = map(int, input().split())
result = dijkstra_heap(K-1)
for i in range(Q):
    x, y = map(int, input().split())
    print(abs(result[x-1]-result[K-1])+abs(result[y-1]+result[K-1]))

Submission status: Accepted

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

n = int(input())
from collections import defaultdict
abc = [tuple(map(int,input().split())) for i in range(n-1)]
es = [[] for i in range(n)]
for a,b,c in abc:
    a,b = a-1,b-1
    es[a].append((b,c))
    es[b].append((a,c))

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

dist = [-1]*n

def dfs(v=0,parent=-1,d=0):
    for next_v,dd in es[v]:
        if dist[next_v] == -1:
            dist[next_v] = d + dd
            dfs(next_v,v,dist[next_v])

dist[k-1] =0
dfs(k-1,-1,0)
ans=[]
for x,y in xy:
    x,y=x-1,y-1
    ans.append(dist[x]+dist[y])

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

Submission status: Accepted

Solution code:
import sys
import heapq
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt
INF = 1 << 60
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def dijkstra_heap(s,edge):
    #始点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 factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

#ここから書き始める
# def dfs(current, goal, cost, visited):
#     if current == goal:
#         return cost
#     if len(tree[current]) == 0:
#         return 0 
#     for i in tree[current]:
#         # print("i =", i)
#         if visited[i[0]] == 0:
#             return dfs(i[0], goal, cost + i[1])

def bfs(queue):
    visited = [0] * n
    while queue:
        # print("dist =", dist)
        node = queue.popleft()
        # print("node =", node)
        current = node[0]
        if visited[current] == 0:
            new_cost = node[1]
            cost = node[2]
            cost += new_cost
            dist[current] = min(dist[current], cost)
            visited[current] = 1
            for i in tree[current]:
                queue.append([i[0], i[1], cost])

n = int(input())
tree = [[] for i in range(n)]
for i in range(n - 1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    tree[a].append([b, c])
    tree[b].append([a, c])
# print(tree)
q, k = map(int, input().split())
k -= 1
dist = [INF] * n
# visited = [0] * n
queue = deque([[k, 0, 0]])
# print(queue)
bfs(queue)
# print("dist =", dist)
ans = [0] * q
for i in range(q):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    ans[i] = dist[x] + dist[y]
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
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((c, b))
    edges[b].append((c, a))
INF = float('inf')


def dfs(v, parent, distance):
    dist[v] = distance
    for d, v2 in edges[v]:
        if parent == v2:
            continue
        dfs(v2, v, distance+d)


q, k = map(int, input().split())
dist = [INF]*n
dfs(k-1, -1, 0)
for _ in range(q):
    x, y = map(lambda x: int(x)-1, input().split())
    print(dist[x]+dist[y])

Submission status: Accepted

Solution code:
import sys
import heapq
input = sys.stdin.readline
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((c, b))
    edges[b].append((c, a))
INF = float('inf')


def dijkstra(init_v):
    dist = [INF]*n
    dist[init_v] = 0
    tasks = [(0, init_v)]
    while tasks:
        d, v = heapq.heappop(tasks)
        if dist[v] < d:
            continue
        for d2, v2 in edges[v]:
            if dist[v2] <= dist[v]+d2:
                continue
            dist[v2] = dist[v]+d2
            heapq.heappush(tasks, ((dist[v2], v2)))
    return dist


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

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
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((c, b))
    edges[b].append((c, a))
INF = float('inf')


def bfs(init_v):
    dist = [INF]*n
    dist[init_v] = 0
    tasks = deque([(0, init_v)])
    while tasks:
        d, v = tasks.popleft()
        for d2, v2 in edges[v]:
            if dist[v2] <= dist[v]+d2:
                continue
            dist[v2] = dist[v]+d2
            tasks.append((dist[v2], v2))
    return dist


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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
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((c, b))
    edges[b].append((c, a))
INF = float('inf')


def dfs(init_v):
    dist = [INF]*n
    dist[init_v] = 0
    tasks = [(0, init_v)]
    while tasks:
        d, v = tasks.pop()
        for d2, v2 in edges[v]:
            if dist[v2] <= dist[v]+d2:
                continue
            dist[v2] = dist[v]+d2
            tasks.append((dist[v2], v2))
    return dist


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

Submission status: Accepted

Solution code:
from heapq import heapify, heappush, heappop

import sys
sys.setrecursionlimit(100000000)

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

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

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

# # 頂点KからDFSする
# d = [None for _ in range(n + 1)]
# d[K] = 0

# def dfs(v, dist):
#     for (u, cvu) in G[v]:
#         if d[u] is None:
#             d[u] = dist + cvu
#             dfs(u, dist + cvu)

# dfs(K, 0)

# 頂点KからDFSする (heap ver.)
queue = []
d = [None for _ in range(n + 1)]
heappush(queue, (0, K, -1))
while len(queue) > 0:
    dist, index, parent = heappop(queue)
    if d[index] is not None:
        continue
    d[index] = dist
    for (u, cvu) in G[index]:
        if u == parent:
            continue
        heappush(queue, (dist + cvu, u, index))

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

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    N = int(input())
    inf = 10**17

    def dijkstra_heap(start,edge):
        #始点から各頂点への最短距離(頂点番号:0~N-1)
        d = [inf]*N
        used = [False]*N
        d[start] = 0
        used[start] = True
        edgelist = []
        #a:重み(//), b:次の頂点(%)
        for a,b in edge[start]:
            heappush(edgelist,a*(10**6)+b)

        while len(edgelist):
            #まだ最短距離が決まっていない頂点の中から最小の距離のものを探す
            minedge = heappop(edgelist)
            if used[minedge%(10**6)]:
                continue
            node = minedge%(10**6)
            d[node] = minedge//(10**6)
            used[node] = True

            for e in edge[node]:
                if not used[e[1]]:
                    heappush(edgelist,(e[0]+d[node])*(10**6)+e[1])
        return d

    #N:頂点数   W:辺数
    edge = [[] for i in range(N)]
    #edge[i] : iから出る道の[重み,行先]の配列
    for _ in range(N-1):
        x,y,z = map(int,input().split())
        edge[x-1].append((z,y-1))
        edge[y-1].append((z,x-1))

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    N = int(input())
    
    def dfs(v):
        visited[v] = 1
        for cost, nv in edge[v]:
            if visited[nv] == 1:
                continue
            d[nv] = d[v] + cost
            dfs(nv)

    #N:頂点数   W:辺数
    edge = [[] for i in range(N)]
    #edge[i] : iから出る道の[重み,行先]の配列
    for _ in range(N-1):
        x,y,z = map(int,input().split())
        edge[x-1].append((z,y-1))
        edge[y-1].append((z,x-1))

    q,k = map(int, input().split())
    d = [-1]*N
    d[k-1] = 0
    visited = [0]*N
    dfs(k-1)

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    N = int(input())
    inf = 10**17

    def dijkstra_heap(start,edge):
        #始点から各頂点への最短距離(頂点番号:0~N-1)
        d = [inf]*N
        used = [False]*N
        d[start] = 0
        used[start] = True
        edgelist = []
        #a:重み(//), b:次の頂点(%)
        for a,b in edge[start]:
            heappush(edgelist,a*(10**6)+b)

        while len(edgelist):
            #まだ最短距離が決まっていない頂点の中から最小の距離のものを探す
            minedge = heappop(edgelist)
            if used[minedge%(10**6)]:
                continue
            node = minedge%(10**6)
            d[node] = minedge//(10**6)
            used[node] = True

            for e in edge[node]:
                if not used[e[1]]:
                    heappush(edgelist,(e[0]+d[node])*(10**6)+e[1])
        return d

    #N:頂点数   W:辺数
    edge = [[] for i in range(N)]
    #edge[i] : iから出る道の[重み,行先]の配列
    for _ in range(N-1):
        x,y,z = map(int,input().split())
        edge[x-1].append((z,y-1))
        edge[y-1].append((z,x-1))

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

# Kからの最短距離を計算
dist = [-1 for i in range(N)]
que = []
heapq.heappush(que, (0, K - 1, -1)) # (distance, index, parent)
while len(que) > 0:
    d, ind, par = heapq.heappop(que)
    if dist[ind] != -1:
        continue
    dist[ind] = d
    for edge in edges[ind]:
        if edge[0] == par:
            continue
        heapq.heappush(que, (d + edge[1], edge[0], ind))

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

Submission status: Accepted

Solution code:
import heapq

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

# Kからの最短距離を計算
dist = [-1 for i in range(N)]
que = []
heapq.heappush(que, (0, K - 1, -1)) # (distance, index, parent)
while len(que) > 0:
    d, ind, par = heapq.heappop(que)
    if dist[ind] != -1:
        continue
    dist[ind] = d
    for edge in edges[ind]:
        if edge[0] == par:
            continue
        heapq.heappush(que, (d + edge[1], edge[0], ind))

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

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

import heapq


def dijkstra_heap(s, edge):
    # 始点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


n = int(readline())
edge = [[] for i in range(n)]
for i in range(n - 1):
    a, b, c = map(int, readline().split())
    edge[a - 1].append([c, b - 1])
    edge[b - 1].append([c, a - 1])
q, k = map(int, readline().split())
check = dijkstra_heap(k - 1, edge)
for i in range(q):
    x, y = map(int, readline().split())
    print(check[x - 1] + check[y - 1])