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


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

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

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

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

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

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

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
import heapq
input=sys.stdin.readline
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [input() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')


def main():
    # ダイクストラ
    def dijkstra(start, edge):
        costs=[inf]*N
        costs[start]=0
        hash={}
        queue=[(0, start)]  # 第一要素が優先的に評価されるので
        while queue:
            c, v=heapq.heappop(queue)
            if v in hash:
                continue
            hash[v]=1
            costs[v]=c
            for node, cost in edge[v]:
                if node in hash:
                    continue
                heapq.heappush(queue, (c + cost, node))

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

    
    
    
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
import heapq
input=sys.stdin.readline
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [input() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')


def main():
    # ダイクストラ
    def dijkstra(start, edge):
        costs=[inf]*N
        costs[start]=0
        hash={}
        queue=[(0, start)]  # 第一要素が優先的に評価されるので
        while queue:
            c, v=heapq.heappop(queue)
            if v in hash:
                continue
            hash[v]=1
            costs[v]=c
            for node, cost in edge[v]:
                if node in hash:
                    continue
                heapq.heappush(queue, (c + cost, node))

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

    
    
    
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import collections

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

Submission status: Accepted

Solution code:
N = int(input())

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

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

vi = K-1 #時と場合によってここを変える
from collections import deque
Q = deque([vi])
checked_list = [False for i in range(N)]
checked_list[vi]=True
min_path_list = [10**27 for i in range(N)] #問題によりここを変える
min_path_list[vi] = 0
while len(Q)>0:
    v = Q.pop()
    for e in e_list[v]:
        v1,c=e
        if not checked_list[v1]:
            checked_list[v1]=True
            Q.append(v1)
            min_path_list[v1]=min(min_path_list[v1],min_path_list[v]+c) #問題によりここを変える

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

Submission status: Accepted

Solution code:
import sys

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

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

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

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

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

Submission status: Accepted

Solution code:
import heapq
import sys

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

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


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

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

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

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


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

dists = dijkstra(graph, K)

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

Submission status: Accepted

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


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

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

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

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

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

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

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

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

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

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

d = Dijkstra(g, k)   #0から

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

for i in ans:
    print(i)

Submission status: Accepted

Solution code:
import sys
import collections
input = sys.stdin.readline
N = int(input())
tree = [[] for _ in range(N+1)]
tree_cost = [1000000001 for _ in range(N+1)]
for _ in range(N-1):
    a, b, c = map(int, input().split())
    tree[a].append([b, c])
    tree[b].append([a, c])
Q, K = map(int, input().split())

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

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

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

Submission status: Accepted

Solution code:
N = int(input())
G = [[] for i in range(N)]
for i in range(N-1):
    u,v,w = map(int,input().split())
    # グラフに頂点と距離を追加
    G[u-1].append((v-1,w))
    G[v-1].append((u-1,w))

from collections import deque



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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

dfs(k,-1,0)

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

Submission status: Accepted

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

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

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

dfs(k,-1,0)

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

Submission status: Accepted

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

Submission status: Accepted

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

    # 距離をinfで初期化
    d = [inf for i in range(v)]
    d[s] = 0

    # sへの距離は0
    q = [[0,s]]
    heapq.heapify(q)

    # 距離が最小の頂点から更新していけば
    # p[1]から行ける
    while q:
        p = heapq.heappop(q)

        # 頂点p[1]までの距離がheapないのp[1]までの距離より小さい場合、continue
        if d[p[1]]<p[0]:
            continue

        # 頂点p[1]から伸びる、全ての辺の距離を確認
        for i in range(len(path[p[1]])):
            # 頂点p[1]から行ける頂点の距離がp[1]までの距離とp[1]からの距離の和より小さい場合 -> 距離を更新し、heapに追加
            if d[path[p[1]][i][1]] > d[p[1]] + path[p[1]][i][0]:
                d[path[p[1]][i][1]] = d[p[1]]+path[p[1]][i][0]
                heapq.heappush(q,[d[path[p[1]][i][1]], path[p[1]][i][1]])
    return d


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

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

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

d = dijkstra(n,k,p)

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

Submission status: Accepted

Solution code:
from heapq import heappop, heappush


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


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

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline

N = int(input())
tree_dict = defaultdict(set)
cost_dict = dict()
for i in range(N-1):
    a, b, c = tuple(map(int, input().split()))
    tree_dict[a] |= {(b, c)}
    tree_dict[b] |= {(a, c)}
    cost_dict[(a, b)] = c
    cost_dict[(b, a)] = c

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

# calc dist from K
dist = {K: 0}
q = [(to_node, K) for to_node, cost in tree_dict[K]]
for i in range(N - 1):
    to_node, from_node = q[i]
    dist[to_node] = dist[from_node] + cost_dict[(from_node, to_node)]
    for next_node, cost in tree_dict[to_node]:
        if next_node != from_node:
            q += [(next_node, to_node)]


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

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())

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

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

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

K -= 1

DISTANCE = [float("inf") for i in range(N)]

DISTANCE[K] = 0

q = deque([K])

while q :
    from_ = q.popleft()
    for to_, weight in L[from_] :
        dist = DISTANCE[from_] + weight
        if dist < DISTANCE[to_] :
            DISTANCE[to_] = dist
            q.append(to_)
            
ans = []

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

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

Submission status: Accepted

Solution code:
n = int(input())
g = {}
from collections import deque
for i in range(1,n+1):
    g[i] = deque([])
for _ in range(n-1):
    a,b,c = map(int,input().split())
    g[a].appendleft([b,c])
    g[b].appendleft([a,c])
Q,k = map(int,input().split())
q = [list(map(int,input().split())) for _ in range(Q)]
queue = deque(g[k])
shortest = [0]*(n+1)
while queue:
    a,c = queue.pop()
    shortest[a] = c
    while g[a]:
        v = g[a].pop()
        if shortest[v[0]]==0:
            queue.appendleft([v[0],v[1]+c])
for x,y in q:
    print(shortest[x]+shortest[y])

Submission status: Accepted

Solution code:
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)]

adjacent_dict={i:{} for i in range(1,N+1)}
for a,b,c in ABC:
  adjacent_dict[a][b]=c
  adjacent_dict[b][a]=c

from collections import deque
fromK = [0]*(N+1)
stack = deque([K])
while stack:
  k = stack.popleft()
  for v, d in adjacent_dict[k].items():
    if fromK[v] == 0:
      fromK[v] = fromK[k]+d
      stack.append(v)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit 
N = int(input())
# 再帰の深さを増やしておく
sys.setrecursionlimit(10**9+1)

nodes = [[] for _ in range(N+1)]
for i in range(N-1):
      a,b,c, = map(int, input().split())
      # a->bとb->aの両方について保存
      nodes[a].append((b,c))
      nodes[b].append((a,c))

memo = [0] * (N+1)

# searchedというdistを持たせて調べた場所を管理するのも可能か
def dfs(cur, prev, dist):
      # ある地点（K）から現在地点までのコストを記入しておくことで、最終的にKから他のノードまでの距離が記入される
      memo[cur] = dist
      # nodes[a]から移動できる先と距離を取り出す
      for next, cost in nodes[cur]:
            # 移動前に戻ると無限ループするので飛ばす。searchedなりを持たせてもいい
            if next == prev:
                  continue
            # 移動先について探索を行う
            dfs(next, cur, dist+cost)

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

Submission status: Accepted

Solution code:
import collections

n=int(input())
arr=[[] for _ in range(n+1)]
for i in range(n-1):
  u,v,w=map(int,input().split())
  arr[u].append([v,w])
  arr[v].append([u,w])
m,p=map(int,input().split())
q=collections.deque([p])
check=[False for _ in range(n+1)]
check[p]=True
d=[0 for _ in range(n+1)]
while 1:
  if len(q)==0:
    break
  tmp=q.popleft()
  for i,j in arr[tmp]:
    if check[i]==False:
      check[i]=True
      d[i]=d[tmp]+j
      q.append(i)
for i in range(m):
  u,v=map(int,input().split())
  print(d[u]+d[v])

Submission status: Accepted

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

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

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

dist = [None]*(N+1)

def set_dist(x,d):
  dist[x] = d
  for y,dd in edge[x]:
    if dist[y] is not None:
      continue
    set_dist(y,d+dd)

set_dist(K,0)

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

Submission status: Accepted

Solution code:
n=int(input())
Edges=[]
for i in range(n-1):
  a,b,c=map(int,input().split())
  Edges.append([a,b,c])
q,k=map(int,input().split())
def BFS(K,edges,N):
  roots=[[] for i in range(n)]
  for a,b,c in edges:
    roots[a-1]+=[(b-1,c)]
    roots[b-1]+=[(a-1,c)]
  dist=[-1]*n
  stack=[]
  stack.append(K)
  dist[K]=0
  while stack:
    label=stack.pop(-1)
    for i,c in roots[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        stack+=[i]
  return dist
D=BFS(k-1,Edges,n)
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
input = sys.stdin.readline
n=int(input())
Edges=[]
for i in range(n-1):
  a,b,c=map(int,input().split())
  Edges.append([a,b,c])
q,k=map(int,input().split())
def BFS(K,edges,N):
  roots=[[] for i in range(n)]
  for a,b,c in edges:
    roots[a-1]+=[(b-1,c)]
    roots[b-1]+=[(a-1,c)]
  dist=[-1]*n
  stack=[]
  stack.append(K)
  dist[K]=0
  while stack:
    label=stack.pop(-1)
    for i,c in roots[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        stack+=[i]
  return dist
D=BFS(k-1,Edges,n)
for i in range(q):
  x,y=map(int,input().split())
  print(D[x-1]+D[y-1])

Submission status: Accepted

Solution code:
N = int(input())

ed = [ [ int(it) for it in input().split() ] for i in range(N-1) ]
Q,K = [ int(it) for it in input().split() ]
qu = [ [ int(it)-1 for it in input().split() ] for i in range(Q) ]

K = K-1
down = [ [] for i in range(N) ]
for a,b,c in ed:
  down[a-1].append( (b-1,c) )
  down[b-1].append( (a-1,c) )

dist = [10000000000000000000000]*N
dist[K] = 0

now = [K]
for i in range(100000000000000):
  if ( len(now) == 0 ):
    break
  n = now.pop()
  for d,c in down[n]:
    dist[d] = min( dist[d] , dist[n] + c )
    now.append(d)
  down[n] = []
  
for a,b in qu:
  print ( dist[a]+dist[b] )

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

N = int(input())

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


Q, K = [int(i) for i in input().split()]
dist = [0] * (N + 1)
def dfs(cur, parent, d):
    dist[cur] = d
    for to, cost in E[cur]:
        if to == parent:
            continue
        dfs(to, cur, d + cost)
dfs(K, -1, 0)

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

Submission status: Accepted

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

Q, K = map(int, input().split())
XY = []
for _ in range(Q):
    x,y = map(int, input().split())
    XY.append((x,y))
    
edges = ABC[:]

graph = {}
for a,b,c in edges:
    if not a in graph:
        graph[a] = {}
    if not b in graph:
        graph[b] = {}
    graph[a][b] = c
    graph[b][a] = c


from heapq import heappush, heappop

def dijkstra(graph, start):
    A = [None] * (N+1)
    queue = [(0, start)]
    while queue:
        path_len, v = heappop(queue)
        if A[v] is None: # v is unvisited
            A[v] = path_len
            for w, edge_len in graph[v].items():
                if A[w] is None:
                    heappush(queue, (path_len + edge_len, w))

    # to give same result as original, assign zero distance to unreachable vertices             
    return [0 if x is None else x for x in A]

shortest = dijkstra(graph, K)
#print(shortest)

questions = XY

for x,y in questions:
    ans = shortest[x] + shortest[y]
    print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2*10**5)
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] += (b,c),
    G[b] += (a,c),
q, k = map(int,input().split())
d = [0]*(n+1) #kから各点への距離
def f(v,p,u): #v:今見ているとこ p:一つ前に見たとこ u:kからの距離
    d[v] = u
    for t, c in G[v]:
        if p != t:
            f(t,v,u+c)
f(k,0,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**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] += (b,c),
    G[b] += (a,c),
q, k = map(int,input().split())
d = [0]*(n+1) #kから各点への距離
def f(v,p,u): #v:今見ているとこ p:一つ前に見たとこ u:kからの距離
    d[v] = u
    for t, c in G[v]:
        if p != t:
            f(t,v,u+c)
f(k,0,0)
for i in range(q):
    x, y = map(int,input().split())
    print(d[x]+d[y])

Submission status: Accepted

Solution code:
from collections import defaultdict
from heapq import heappop, heappush


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

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

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

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

    def get_nodes(self):
        return self.graph.keys()


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

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

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

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

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


g = Graph()

N = int(input())

rows = []
cols = []
weights = []

for _ in range(N-1):
    # u v 間のコスト
    u, v, a = [int(i) for i in input().split()]
    g.add_edge(u-1, v-1, a)
    g.add_edge(v-1, u-1, a)

Q, K = [int(i) for i in input().split()]
d = Dijkstra(g, K-1)

#print(g)
#print(d.dist)
for i in range(Q):
    x, y = [int(i) for i in input().split()]
    print(d.dist[x-1]+d.dist[y-1])

Submission status: Accepted

Solution code:
from collections import defaultdict
from heapq import heappop, heappush


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

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

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

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

    def get_nodes(self):
        return self.graph.keys()


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

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

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

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

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


g = Graph()

N = int(input())

rows = []
cols = []
weights = []

for _ in range(N-1):
    # u v 間のコスト
    u, v, a = [int(i) for i in input().split()]
    g.add_edge(u-1, v-1, a)
    g.add_edge(v-1, u-1, a)

Q, K = [int(i) for i in input().split()]
d = Dijkstra(g, K-1)

#print(g)
#print(d.dist)
for i in range(Q):
    x, y = [int(i) for i in input().split()]
    print(d.dist[x-1]+d.dist[y-1])