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 heapq
def dijkstra_heap(s):
    d = [float("inf")] * n
    used = [True] * n #True: not used
    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
import sys
input = sys.stdin.readline
n =int(input())
 
edge = [[] for i in range(n)]
#edge[i] : [weght,to]
for i in range(n-1):
    a, b, c = map(int,input().split())
    a, b = a-1, b-1
    edge[a].append((c,b))
    edge[b].append((c,a)) 
q, k = map(int, input().split())
k = k-1
d = dijkstra_heap(k)
for i in range(q):
  x, y = map(int, input().split())
  x, y = x-1, y-1
  print(d[x]+d[y])

Submission status: Accepted

Solution code:
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

import heapq
BIGDI = 10**18

# N nodes  M arcs  go from S to T (node# starts from 1)
n = inn()
dst = [{} for i in range(n+1)]
for i in range(n-1):
    u,v,a = inm()
    dst[u][v] = a
    dst[v][u] = a

qq,k = inm()

cost = [BIGDI]*(n+1)
q = [(0,k)]
while len(q)>0:
    d,p = heapq.heappop(q)
    if cost[p]<=d:
        continue
    cost[p] = d
    for v in dst[p]:
        heapq.heappush(q,(d+dst[p][v], v))

# cost[t-1] is the answer

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

Submission status: Accepted

Solution code:
from collections import deque

def bfs(graph,root,distK):
    visited = set([root])       # 訪問済みノードを管理する 
    queue = deque([root]) # 訪れるべきノードを管理するqueueを作成
    while queue:          # list queueが空になるまで行う
        vertex = queue.popleft()         # 頂点を極める
        for neighbour in graph[vertex]:  # 頂点の近隣のノードに調べる
            node = neighbour[0]
            dist = neighbour[1]
            if node not in visited:
                visited.add(node)
                queue.append(node)
                distK[node] = distK[vertex] + dist
    return distK

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

Q,K = map(int,input().split())
distK = {K:0}
distK = bfs(graph,K,distK)
for _ in range(Q):
    x,y = map(int,input().split())
    print(distK[x] + distK[y])

Submission status: Accepted

Solution code:
from collections import deque
inf=100000000000000000000
N = input()
N = int(N)
path=[[] for i in range(N)]
for fuga in range(N-1):
    a,b,c=map(int, input().split())
    path[a-1].append([b-1,c])
    path[b-1].append([a-1,c])
Q,K=map(int, input().split())
stack=deque()
stack.append(K-1)
Kcost=[0]*N#あとあと初期化
went=[False]*N
went[K-1]=True
while stack:
    cur=stack.pop()
    curcost=Kcost[cur]
    for next,c in path[cur]:
        if c and not went[next]:
            went[next]=True
            Kcost[next]=curcost+c
            stack.append(next)
for q in range(Q):
    x,y=map(int, input().split())
    print(Kcost[x-1]+Kcost[y-1])

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

from heapq import heappop, heappush

def dijkstra(E, start):
    N_d = len(E)
    dist = [INF] * N_d
    dist[start] = 0
    q = [(0, start)]
    while q:
        dist_v, v = heappop(q)
        if dist[v] != dist_v:
            continue
        for u, dist_vu in E[v]:
            dist_u = dist_v + dist_vu
            if dist_u < dist[u]:
                dist[u] = dist_u
                heappush(q, (dist_u, u))
    return dist

N = INT()
abc = [LIST() for i in range(N-1)]
Q, K = MAP()
xy = [LIST() for i in range(Q)]

graph = defaultdict(list)

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

    # graph[a-1].append((b-1, c))

d = dijkstra(graph, K-1)

for x, y in xy:
    # ans = dijkstra(graph, x-1)[K-1] + dijkstra(graph, K-1)[y-1]
    # d = dijkstra(graph, K-1)
    
    ans = d[x-1] + d[y-1]
    # dijkstra(graph, x-1)
    print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
path = [LIST() for _ in range(N - 1)]
Q, K = MAP()
question = [LIST() for _ in range(Q)]

graph = [[] for i in range(N)]

for i in range(N - 1):
	graph[path[i][0] - 1].append([path[i][1] - 1, path[i][2]])
	graph[path[i][1] - 1].append([path[i][0] - 1, path[i][2]])

depth = [0]*N

q = deque([K - 1])
connect = [0]*N
connect[K - 1] = 1
while q:
	n = q.popleft()
	for node, length in graph[n]:
		if connect[node] == 0:
			connect[node] = 1
			depth[node] = length + depth[n]
			q.append(node)

for i in range(Q):
	print(depth[question[i][0] - 1] + depth[question[i][1] - 1])

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
l = [[] for _ in range(N)]
p = [0]*N
e = [0]*N
q = []

for _ in range(N-1):
    fi, si, wi = tuple(LIST())
    l[fi-1].append([si-1, wi])
    l[si-1].append([fi-1, wi])
Q, K = tuple(LIST())
for _ in range(Q):
    q.append(LIST())

def f(n, w):
    p[n] = 1
    e[n] = w
    for next_node in l[n]:
        nn, nw = tuple(next_node)
        if p[nn] == 0:
            f(nn, w+nw)
f(K-1, 0)
for nodes in q:
    fi, si = tuple(nodes)
    print(e[fi-1]+e[si-1])

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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

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


def dijkstra(s,n,g):
    # g[i][j] : the cost of i→j  or g[i] = [(target, cost), ...]
    # must import heapq
    d = [10**18] * n
    d[s] = 0
    q = [(0,s)]
    while q:
        dist_u, u = heappop(q)
        if d[u] < dist_u:
            continue
        for v, c in g[u]:  # 'in g[u]' if g is an adj list.
            if d[v] > dist_u + c:
                d[v] = dist_u + c
                heappush(q, (d[v], v))
    return d




q, k = map(int, input().split())
d = dijkstra(k-1, n, g)

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

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
n = int(input())
g = [[] for _ in range(n)]

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


def dijkstra(s,n,g):
    # g[i][j] : the cost of i→j  or g[i] = [(target, cost), ...]
    # must import heapq
    d = [10**18] * n
    d[s] = 0
    q = [(0,s)]
    while q:
        dist_u, u = heappop(q)
        if d[u] < dist_u:
            continue
        for v, c in g[u]:  # 'in g[u]' if g is an adj list.
            if d[v] > dist_u + c:
                d[v] = dist_u + c
                heappush(q, (d[v], v))
    return d




q, k = map(int, input().split())
d = dijkstra(k-1, n, g)

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

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
n = int(input())
g = [[] for _ in range(n)]

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


def dijkstra(s, n, edges):
    # edges[i][j] : the cost of i→j
    # import 'heap'
    d = [10**18] * n
    d[s] = 0
    q = [(0, s)]
    while q:
        dist_u, u = heappop(q)
        if d[u] < dist_u:
            continue
        for v, c in edges[u]:
            if d[v] > dist_u + c:
                d[v] = dist_u + c
                heappush(q, (d[v], v))
    return d


q, k = map(int, input().split())
d = dijkstra(k-1, n, g)

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

Submission status: Accepted

Solution code:
from collections import deque

def bfs(i):
    d[i] = 0
    q = deque()
    q.append(i)
    c = 1
    while True:
        if c == n:
            break
        p = q.popleft()
        c += 1
        h = G[p]
        for j in range(len(h)):
            if d[h[j]] == -1:
                q.append(h[j])
                v = w[p]
                d[h[j]] = d[p] + v[j]

n = int(input())
G = ["-1"] * n
w = ["-1"] * n
for _ in range(n - 1):
    a, b, c = map(int, input().split())
    if G[a - 1] == "-1":
        G[a - 1] = [b - 1]
        w[a - 1] = [c]
    else:
        G[a - 1].append(b - 1)
        w[a - 1].append(c)
    if G[b - 1] == "-1":
        G[b - 1] = [a - 1]
        w[b - 1] = [c]
    else:
        G[b - 1].append(a - 1)
        w[b - 1].append(c)

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

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

import sys
sys.setrecursionlimit(10**9)

def main():
  n = int(input())
  inode2scores = [0] * (n+1)
  tree = [[] for _ in range(n+1)]
  weights = dict()
  for _ in range(n-1):
    a, b, c = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)
    weights[(a, b)] = weights[(b, a)] = c
    
  q, k = map(int, input().split())  
  visited = [False] * (n+1)
  iroot = k
  def dfs(inode, score=0):
    visited[inode] = True
    for ichild in tree[inode]:
      if visited[ichild]:
        continue
      inode2scores[ichild] = weights[(inode, ichild)] + score
      dfs(ichild, inode2scores[ichild])
  dfs(iroot)
  for _ in range(q):
    x, y = map(int, input().split())
    print(inode2scores[x] + inode2scores[y])

if __name__=='__main__':
  main()

Submission status: Accepted

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

n = int(input())
G = [[] for _ 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])

vis = [False] * n
d = [-1] * n
def dfs(k, depth):
    vis[k] = True
    d[k] = depth
    for i in G[k]: # i: [to, cost]
        if not vis[i[0]]: dfs(i[0], depth + i[1])

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

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)

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

Q, K = map(int, input().split())
K -= 1
dist = [pow(10, 9) + 1] * N
dist[K] = 0


def dfs(s, before=-1):
    for edge in edges[s]:
        to = edge[0]
        c = edge[1]
        if to != before:
            dist[to] = dist[s] + c
            dfs(to, s)


dfs(K)
for _ in range(Q):
    x, y = map(int, input().split())
    x, y = x-1, y-1
    print(dist[x] + dist[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


depths = dfs(k-1)

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

Submission status: Accepted

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


class Tree:
    WHITE = 0
    GRAY = -1
    BLACK = 1

    def __init__(self, adj):
        n = len(adj)
        self.adj = adj
        self.colors = [self.WHITE] * n
        self.depths = [-1] * n
        self.depth = 0

    def init(self):
        self.__init__(self.adj)

    def dfs(self, u):
        if self.colors[u] == self.BLACK:
            return

        self.colors[u] = self.GRAY
        self.depths[u] = self.depth

        for v, w in self.adj[u]:
            if self.colors[v] == self.WHITE:
                self.depth += w
                self.dfs(v)
                self.depth -= w

        self.colors[u] = self.BLACK


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

tree = Tree(adj)
tree.dfs(k-1)

for x, y in xy:
	x -= 1
	y -= 1
	ans = tree.depths[x] + tree.depths[y]
	print(ans)

Submission status: Accepted

Solution code:
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())
from collections import deque
dist=[-1]*(N+1)
dist[K]=0
q=deque()
q.append(K)

while len(q):
    p=q.popleft()
    for x,c in G[p]:
        if dist[x]!=-1:
            continue
        dist[x]=dist[p]+c
        q.append(x)

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

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

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

distance_map = defaultdict(dict)

for a, b, c in ABC:
    distance_map[a][b] = c
    distance_map[b][a] = c

k_dist = {K: 0}

target = deque(distance_map[K].items())
while target:
    t, distance = target.pop()
    k_dist[t] = distance
    for v in map(lambda x: (x[0], x[1] + distance),filter(lambda x: x[0] not in k_dist, distance_map[t].items())):
        target.append(v)

# print(k_dist)

for x,y in XY:
    print(k_dist[x]+k_dist[y])

Submission status: Accepted

Solution code:
n=int(input())
cd=[[]for _ in range(n)]
for i in range(n-1):
	a,b,c=map(int,input().split())
	cd[a-1].append([b,c])
	cd[b-1].append([a,c])
q,k=map(int,input().split())
from collections import deque
dis=[-1]*n
dis[k-1]=0
stack=deque([k])
while stack:
	p=stack.popleft()
	for i in range(len(cd[p-1])):
		if dis[cd[p-1][i][0]-1]==-1:
			dis[cd[p-1][i][0]-1]=dis[p-1]+cd[p-1][i][1]
			stack.append(cd[p-1][i][0])
for i in range(q):
	x,y=map(int,input().split())
	print(dis[x-1]+dis[y-1])

Submission status: Accepted

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


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


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

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

for g in range(q):
    print(ans_list[g])

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
##########################################
import heapq
class Dijkstra():
    """
    ・有向 / 無向は問わない(無向の場合は，逆向きの辺もたす)
    ・負のコストがない場合のみ
    ・計算量はO(E log|V|)　
    ・heapを使うことで頂点を走査する必要がなくなる（代わりに，距離更新したものは確定でなくともqueに入れておく）
    """
    
    #最短のpathをたす
    
    
    class Edge():
        #重み付き有向辺
        
        def __init__(self, _to, _cost):
            self.to =_to
            self.cost = _cost
    
    def __init__(self, V):
        #引数Vは頂点数
        self.G = [[] for _ in range(V)] #隣接リストG[u][i]が頂点uのi番目の辺
        self. _E = 0 #辺の数
        self._V = V #頂点数
    
    #proparty - 辺の数
    def E(self):
        return self._E
    
    #proparty - 頂点数
    def V(self):
        return self._V
    
    def add(self, _from, _to, _cost):
        #2頂点と辺のコストを追加
        self.G[_from].append(self.Edge(_to,_cost))
        self._E +=1
        
    def add2(self, _from, _to, _cost):
        #2頂点と辺のコスト（無向）を追加
        self.G[_from].append(self.Edge(_to, _cost))
        self.G[_to].append(self.Edge(_from, _cost))
        self._E +=1
        
    def shortest_path(self,s,g):
        #始点sから頂点iまでの最短経路長のリストを返す
        
        que = [] #priority queue
        d = [float("inf")] * self.V()
        prev = [None]*self.V() #prev[j]は，sからjへ最短経路で行くときのjの一つ前の場所
        d[s] = 0
        heapq.heappush(que,(0,s)) #始点の距離と頂点番号をヒープに追加
        
        while len(que)!=0:
            #キューに格納されてある中で一番コストが小さい頂点を取り出す
            cost,v = heapq.heappop(que)
            
            #キューに格納された最短経路長候補がdの距離よりも大きい場合に処理をスキップ
            if d[v] < cost:
                continue
                
            #頂点vに隣接する各頂点iに対して，vを経由した場合の距離を計算して，これがd[i]よりも小さい場合に更新
            for i in range(len(self.G[v])):
                e = self.G[v][i] #vのi個目の隣接辺
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost #更新
                    prev[e.to] = v
                    heapq.heappush(que,(d[e.to],e.to)) #queに新たな最短経路長候補を追加
        
        #sからgまでの最短経路
        path = []
        pos = g #今いる場所，ゴールで初期化
        for _ in range(self.V()+1):
            path.append(pos)
            if pos == s:
                break
            #print("pos:",format(pos))
            pos = prev[pos]
        path.reverse()
        #print(path)
                    
        return d#,path
########################

def main():
    mod=10**9+7
    N=I()
    djk = Dijkstra(N)
    for _ in range(N-1):
        a,b,c=MI()
        djk.add2(a-1, b-1, c)
        
    Q,K=MI()
    d=djk.shortest_path(K-1,0)
    for _ in range(Q):
        x,y=MI()
        print(d[x-1]+d[y-1])

main()

Submission status: Accepted

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

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

################################
N = int(input()) # 頂点数
W = N - 1 # 辺の数

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

K_costs = dijkstra_heap(K - 1) # Kから各頂点へのコスト

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

Submission status: Accepted

Solution code:
from collections import deque
n=int(input())
A=[[0]*3 for i in range(n-1)]
B=[[[] for j in range(2)] for i in range(n)]
for i in range(n-1):
  A[i]=list(map(int,input().split()))
  B[A[i][0]-1][0].append(A[i][1]-1)
  B[A[i][0]-1][1].append(A[i][2])
  B[A[i][1]-1][0].append(A[i][0]-1)
  B[A[i][1]-1][1].append(A[i][2])
d=[0]*n
q,k=map(int,input().split())
C=deque([])
C.append(k-1)
E=[0]*n
E[k-1]=1
while len(C)>0:
  a=C[0]
  C.popleft()
  for i in range(len(B[a][0])):
    if E[B[a][0][i]]==0:
      C.append(B[a][0][i])
      d[B[a][0][i]]=d[a]+B[a][1][i]
      E[B[a][0][i]]=1
for i in range(q):
  s,t=map(int,input().split())
  print(d[s-1]+d[t-1])

Submission status: Accepted

Solution code:
import sys

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

depth = [0] * N

def dfs(v, p, d):
    depth[v] = d
    for e in edges[v]:
        if e[0] == p:
            continue
        dfs(e[0], v, d + e[1])


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

dfs(K, -1, 0)

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

Submission status: Accepted

Solution code:
import heapq

n = int(input())
Edge = [[] for _ in range(n+1)]
for _ in range(n-1):
    a, b, c = map(int, input().split())
    # (コスト, 行き先)として追加する
    Edge[a].append([c,b])
    Edge[b].append([c,a])

q, k = map(int, input().split())
XY = []
for _ in range(q):
    x, y = map(int, input().split())
    XY.append([x,y])

# 関数への入力はs(start)とEdgeリスト
def dijkstra_heap(s, Edge):
    Dist = [10**10 for _ in range(n+1)]
    Dist[s] = 0
    Used = [False for _ in range(n+1)]
    Used[s] = True

    Edgelist = []

    for edge in Edge[s]:
        heapq.heappush(Edgelist, edge)

    while len(Edgelist) >= 1:
        minedge = heapq.heappop(Edgelist)
        cost, v = minedge[0], minedge[1]
        if Used[v] == True:
            continue
        Used[v] = True
        Dist[v] = cost

        for next_edge in Edge[v]:
            next_cost = next_edge[0]
            next_v = next_edge[1]
            heapq.heappush(Edgelist, [next_cost + Dist[v], next_v])
    return Dist

# print(Edge)
Dist_k = dijkstra_heap(k, Edge)

for xy in XY:
    x = xy[0]
    y = xy[1]
    ans = Dist_k[x] + Dist_k[y]
    print(ans)

# print(Dist_k)

Submission status: Accepted

Solution code:
import heapq

n = int(input())
Edge = [[] for _ in range(n+1)]
for _ in range(n-1):
    a, b, c = map(int, input().split())
    # (コスト, 行き先)として追加する
    Edge[a].append([c,b])
    Edge[b].append([c,a])

q, k = map(int, input().split())
XY = []
for _ in range(q):
    x, y = map(int, input().split())
    XY.append([x,y])

# 関数への入力はs(start)とEdgeリスト
def dijkstra_heap(s, Edge):
    Dist = [10**10 for _ in range(n+1)]
    Dist[s] = 0
    Used = [False for _ in range(n+1)]
    Used[s] = True

    Edgelist = []

    for edge in Edge[s]:
        heapq.heappush(Edgelist, edge)

    while len(Edgelist) >= 1:
        minedge = heapq.heappop(Edgelist)
        cost, v = minedge[0], minedge[1]
        if Used[v] == True:
            continue
        Used[v] = True
        Dist[v] = cost

        for next_edge in Edge[v]:
            next_cost = next_edge[0]
            next_v = next_edge[1]
            heapq.heappush(Edgelist, [next_cost + Dist[v], next_v])
    return Dist

# print(Edge)
Dist_k = dijkstra_heap(k, Edge)

for xy in XY:
    x = xy[0]
    y = xy[1]
    ans = Dist_k[x] + Dist_k[y]
    print(ans)

# print(Dist_k)

Submission status: Accepted

Solution code:
#17:31
n = int(input())
peer = [[] for _ in range(n)]
for _ in range(n-1):
  a,b,c = map(int,input().split())
  a -= 1
  b -= 1
  peer[a].append([b,c])
  peer[b].append([a,c])
q,k = map(int,input().split())
k -= 1
now = [k]
seen = [0 for _ in range(n)]
way = [0 for _ in range(n)]
seen[k] = 1
while now:
  last = now
  now = []
  for x in last:
    for yc in peer[x]:
      y,c = yc
      if seen[y] == 0:
        seen[y] = 1
        way[y] = way[x] + c
        now.append(y)
#print(way)
for _ in range(q):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  print(way[a]+way[b])

Submission status: Accepted

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    sys.setrecursionlimit(1000000)
    n=int(input())
    edges=[[] for _ in range(n)]
    for i 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())
    k-=1
    
    dist=[10**9+1]*n
    dist[k]=0
    
    def dfs(s,before=-1):
       for edge in edges[s]:
           to=edge[0]
           c=edge[1]
           if to!=before:
               dist[to]=dist[s]+c
               dfs(to,s) 
              
    dfs(k)
    for i in range(q):
        x,y=map(int,input().split())
        x-=1
        y-=1
        print(dist[x]+dist[y])
        
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import heapq
def dijkstra(V, edges, s):
    inf=float('inf')

    dist=[inf]*V
    dist[s]=0
    
    que=[[0,s]]
    heapq.heapify(que) #最小値を管理 [dist[i],i]となる要素

    while  que:
        p=heapq.heappop(que) #距離が最小のものを取り出す
        dis=p[0]
        v=p[1]
        if dist[v] <dis:
            continue
        for edge in edges[v]:
            to_v=edge[0]
            cost=edge[1]
        
            if dist[to_v] > dist[v] + cost:
                dist[to_v]=dist[v]+cost
                heapq.heappush(que,[dist[to_v], to_v])
    
    return dist

def main():
    import sys
    input=sys.stdin.readline
    n=int(input())
    edges=[[] for _ in range(n)]
    for i 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())
    k-=1
   
    dist=dijkstra(n,edges,k)
    for i in range(q):
        x,y=map(int,input().split())
        x-=1
        y-=1
        print(dist[x]+dist[y])
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import heapq
def dijkstra(V, edges, s):
    inf=float('inf')

    dist=[inf]*V
    dist[s]=0
    
    que=[[0,s]]
    heapq.heapify(que) #最小値を管理 [dist[i],i]となる要素

    while  que:
        p=heapq.heappop(que) #距離が最小のものを取り出す
        dis=p[0]
        v=p[1]
        if dist[v] <dis:
            continue
        for edge in edges[v]:
            to_v=edge[0]
            cost=edge[1]
        
            if dist[to_v] > dist[v] + cost:
                dist[to_v]=dist[v]+cost
                heapq.heappush(que,[dist[to_v], to_v])
    
    return dist

def main():
    n=int(input())
    edges=[[] for _ in range(n)]
    for i 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())
    k-=1
   
    dist=dijkstra(n,edges,k)
    for i in range(q):
        x,y=map(int,input().split())
        x-=1
        y-=1
        print(dist[x]+dist[y])
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**9)

def dfs(num,cost):
    visited[num]=cost
    for item in way[num]:
        if visited[item[0]]==-1:
            dfs(item[0],cost+item[1])
    return
    
N=int(input())

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


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