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: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def dfs(G, v, p, dist):
    """G: graph, v: vertex, p: parent"""
    # Loop for each child
    for c, d in G[v]:
        # Avoid multiple access to parent
        if c == p:
            continue
        dist[c] = dist[v] + d
        dfs(G, c, v, dist)


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

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

    for i in range(Q):
        dist_a = [0] * N
        dist_b = [0] * N
        dfs(G, x[i]-1, -1, dist_a)
        dfs(G, K-1, -1, dist_b)
        ans = dist_a[K-1] + dist_b[y[i]-1]
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import *
def dijkstra(s, n, w, cost):
    # s:始点,n:頂点数,w:辺の数,cost:辺ijの重み
    ans = [float('inf')] * n  # 最短距離の記録
    d = [[float('inf'), i] for i in range(n)]
    used = [False] * n  # 一度最短距離を確定した頂点はもう見ない
    ans[s] = 0
    d[s][0] = 0
    heapify(d)

    while d:
        D, V = heappop(d)
        if used[V]: continue
        used[V] = True

        for t, distance in cost[V]:
            ans[t] = min(ans[t], D + distance)
            heappush(d, [ans[t], t])
    return ans

n = int(input())
route_list = [[] for i in range(n)]  # 辺の移動の際のコスト
for i in range(n - 1):
    s, t, d = map(int, input().split())
    route_list[s - 1].append((t - 1, d))
    route_list[t - 1].append((s - 1, d))
# print(route_list)
q, k = map(int,input().split())

stand = dijkstra(k - 1, n, n - 1, route_list)
#print(stand)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(500000)

N = int(input())

tree = [[] 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())

from functools import lru_cache
@lru_cache(maxsize=None)
def dfs(start, end, dist, f=None):
    if start == end:
        return 0
    for n, d in tree[start]:
        if n == f:
            continue
        if n == end:
            return dist + d
        else:
            result = dfs(n, end, dist+d, start)
            if result is not None:
                return result

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

for i in range(Q):
    x, y = xy[i]
    print(dfs(x, K, 0) + dfs(K, y, 0))

Submission status: Time Limit Exceeded

Solution code:
import heapq
 
def dijkstra_heap(s,edge):
    #始点sから各頂点への最短距離
    d = [10**10]*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(input())
n = N
w = N
 
edge = tuple([] for i in range(n))
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(w-1):
    a,b,c = map(int,input().split())
    edge[a-1].append([c,b-1])
    edge[b-1].append([c,a-1])

dist = []
for i in range(N):
    dist.append(dijkstra_heap(i,edge))

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

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import dijkstra
import sys

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

N = int(input())

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

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

dist = dijkstra(graph)

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

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 5 + 10)


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


def resolve():
    # Python3で出すことに注意！
    # floyd_warshall

    # https://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.csgraph.floyd_warshall.html
    # ↑を見ながら細部を埋める
    from scipy.sparse import csr_matrix
    from scipy.sparse.csgraph import dijkstra

    # (i, j)成分はiからjへの直接経路のコスト
    N = int(input())
    graph = [[0] * N for i in range(N)]
    for i in range(N - 1):
        a, b, c = map(int, input().split())
        graph[a - 1][b - 1] = c

    graph = csr_matrix(graph)
    Q, K = map(int, input().split())
    dist_matrix = dijkstra(csgraph=graph, directed=False, indices=K-1, return_predecessors=False)
    # (i, j)成分はiからjへの最短コスト

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


resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():

    # Python3で出すことに注意！
    # floyd_warshall

    # https://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.csgraph.floyd_warshall.html
    # ↑を見ながら細部を埋める
    from scipy.sparse import csr_matrix
    from scipy.sparse.csgraph import dijkstra

    # (i, j)成分はiからjへの直接経路のコスト
    N=int(input())
    graph = [[0]*N for i in range(N)]
    for i in range(N-1):
        a,b,c=map(int,input().split())
        graph[a-1][b-1]=c


    graph = csr_matrix(graph)

    dist_matrix = dijkstra(csgraph=graph, directed=False, return_predecessors=False)
    # (i, j)成分はiからjへの最短コスト
    Q,K=map(int,input().split())
    for i in range(Q):
        x,y=map(int,input().split())
        print(int(dist_matrix[x-1][K-1]+dist_matrix[K-1][y-1]))


resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():

    # Python3で出すことに注意！
    # floyd_warshall

    # https://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.csgraph.floyd_warshall.html
    # ↑を見ながら細部を埋める
    from scipy.sparse import csr_matrix
    from scipy.sparse.csgraph import floyd_warshall

    # (i, j)成分はiからjへの直接経路のコスト
    N=int(input())
    graph = [[0]*N for i in range(N)]
    for i in range(N-1):
        a,b,c=map(int,input().split())
        graph[a-1][b-1]=c


    graph = csr_matrix(graph)

    dist_matrix = floyd_warshall(csgraph=graph, directed=False, return_predecessors=False)
    # (i, j)成分はiからjへの最短コスト
    Q,K=map(int,input().split())
    for i in range(Q):
        x,y=map(int,input().split())
        print(int(dist_matrix[x-1][K-1]+dist_matrix[K-1][y-1]))


resolve()

Submission status: Time Limit Exceeded

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

n = int(input())
adjacency = [[] for i in range(n+1)] #adjacency[i]は頂点iと隣接する頂点のリスト
distance = {} # distance[(i,j)](i,jは隣接した頂点)は頂点i,jを結ぶ辺の長さ
for i in range(n-1):
    line = list(map(int, input().split()))
    adjacency[line[0]].append(line[1])
    adjacency[line[1]].append(line[0])
    distance[(line[0], line[1])] = line[2]
    distance[(line[1], line[0])] = line[2]
q, k = map(int, input().split())
x = []
y = []
for i in range(q):
    line = list(map(int, input().split()))
    x.append(line[0])
    y.append(line[1])

k_distance = [-1 for i in range(n+1)] # k_distance[i]は頂点i,kの距離
k_distance[k] = 0
reached = {k}
def dfs(v, d): # 現在いる頂点vと頂点v,k間の距離dを入力すると頂点vと隣接する未到達の頂点のk_distanceを計算してappendする
    for neighbor in adjacency[v]:
        if not neighbor in reached:
            reached.add(neighbor)
            k_distance[neighbor] = d + distance[(v, neighbor)]
            dfs(neighbor, k_distance[neighbor])
    return
dfs(k, 0)
for i in range(q):
    print(k_distance[x[i]] + k_distance[y[i]])

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
INF=9999999999
d=[INF for _ in range(n)]
dist=[[INF for _ in range(n)] for _ in range(n)]
linked=[[] for _ in range(n)]

for i in range(n):
    dist[i][i]=0

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

def dfs(v,p,dv):
    d[v]=dv
    for i in linked[v]:
        linked[i].remove(v)
        if(i==p):
            continue
        dfs(i,v,dv+dist[v][i])



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

dfs(k-1,-1,0)

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

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
INF=9999999999
d=[INF for _ in range(n)]
dist=[[INF for _ in range(n)] for _ in range(n)]
used=[False for _ in range(n)]
linked=[[] for _ in range(n)]

for i in range(n):
    dist[i][i]=0

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

def dfs(v,dv):
    d[v]=dv
    used[v]=True
    for i in linked[v]:
        linked[i].remove(v)
        if(used[i]):
            continue
        dfs(i,dv+dist[v][i])



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: Time Limit Exceeded

Solution code:
n=int(input())
INF=9999999999
d=[INF for _ in range(n)]
dist=[[INF for _ in range(n)] for _ in range(n)]
used=[False for _ in range(n)]
linked=[[] for _ in range(n)]

for i in range(n):
    dist[i][i]=0

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

def dfs(v,dv):
    d[v]=dv
    used[v]=True
    for i in linked[v]:
        if(used[i]):
            continue
        dfs(i,dv+dist[v][i])



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: Time Limit Exceeded

Solution code:
n=int(input())
INF=9999999999
d=[[INF for _ in range(n)] for _ in range(n)]

for i in range(n):
    d[i][i]=0

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

for a in range(n):
    for b in range(n):
        for c in range(n):
            d[b][c]=min(d[b][c],d[b][a]+d[a][c])



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

Submission status: Time Limit Exceeded

Solution code:
"""
--- アルゴリズム概要 ---
前計算で頂点Kから各ノードへの最短路を記録しておき、
各クエリに対しては、dp[a]+dp[b]を返せばよい。

頂点Kから各ノードへの最短ルートはdfsとかで記録していけばよい。
"""
def main():
    import sys
    sys.setrecursionlimit(20000000)
    input = sys.stdin.readline
    N = int(input())
    AB = [[]for _ in range(N+1)]
    for i in range(N-1):
        a,b,c = map(int,input().split())
        AB[a].append((b,c))
        AB[b].append((a,c))

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

    path = {K:""}
    dp = [0]*(N+1)
    que = []
    for n,c in AB[K]:
        que.append((n,c))
    while que:
        now,cost = que.pop(0)
        path[now]=""
        dp[now]=cost
        for n,c in AB[now]:
            if n not in path:
                que.append((n,cost+c))
    for i in range(Q):
        x,y=map(int,input().split())
        print(dp[x]+dp[y])
main()

Submission status: Time Limit Exceeded

Solution code:
"""
--- アルゴリズム概要 ---
前計算で頂点Kから各ノードへの最短路を記録しておき、
各クエリに対しては、dp[a]+dp[b]を返せばよい。

頂点Kから各ノードへの最短ルートはdfsとかで記録していけばよい。
"""
def main():
    import sys
    sys.setrecursionlimit(20000000)
    input = sys.stdin.readline
    N = int(input())
    AB = [{}for _ in range(N+1)]
    for i in range(N-1):
        a,b,c = map(int,input().split())
        AB[a][b] = c
        AB[b][a] = c

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

    path = {K:""}
    dp = [0]*(N+1)
    def dfs(n,cost):
        path[n]=""
        dp[n]=cost
        for i,c in AB[n].items():
            if i not in path:
                nextcost = cost+c
                dfs(i,nextcost)
    dfs(K,0)
    for i in range(Q):
        x,y=map(int,input().split())
        print(dp[x]+dp[y])
main()

Submission status: Time Limit Exceeded

Solution code:
"""
--- アルゴリズム概要 ---
前計算で頂点Kから各ノードへの最短路を記録しておき、
各クエリに対しては、dp[a]+dp[b]を返せばよい。

頂点Kから各ノードへの最短ルートはdfsとかで記録していけばよい。
"""
import sys
sys.setrecursionlimit(2000000)
input = sys.stdin.readline
N = int(input())
AB = [{}for _ in range(N+1)]
for i in range(N-1):
    a,b,c = map(int,input().split())
    AB[a][b] = c
    AB[b][a] = c

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

path = {K:""}
dp = [0]*(N+1)
def dfs(n,cost):
    path[n]=""
    dp[n]=cost
    for i,c in AB[n].items():
        if i not in path:
            dfs(i,cost+c)
dfs(K,0)
for i in range(Q):
    x,y=map(int,input().split())
    print(dp[x]+dp[y])

Submission status: Time Limit Exceeded

Solution code:
"""
--- アルゴリズム概要 ---
前計算で頂点Kから各ノードへの最短路を記録しておき、
各クエリに対しては、dp[a]+dp[b]を返せばよい。

頂点Kから各ノードへの最短ルートはdfsとかで記録していけばよい。
"""
import sys
sys.setrecursionlimit(2000000)
N = int(input())
AB = [{}for _ in range(N+1)]
for i in range(N-1):
    a,b,c = map(int,input().split())
    AB[a][b] = c
    AB[b][a] = c

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

path = {K:""}
dp = [0]*(N+1)
def dfs(n,cost):
    path[n]=""
    dp[n]=cost
    for i,c in AB[n].items():
        if i not in path:
            dfs(i,cost+c)
dfs(K,0)
for i in range(Q):
    x,y=map(int,input().split())
    print(dp[x]+dp[y])

Submission status: Time Limit Exceeded

Solution code:
"""
---アルゴリズム概要---
閉路のないグラフなので、シンプルにxからKまでまっすぐに進んでから、Kからyにまっすぐ進むことを考えればよい。
クエリの数Qが10**5個あるので、ノードaからノードbにまっすぐ進む場合のコストをメモしていくのがよさそう。

次に、どうやってノードaからノードbへの「まっすぐ進む道」＝「まっすぐ進むための次のノード」を判断するかだが、
これは、ノードaが直接つながっているノードのうち、
ノードbへのコストが最も少ないものがまっすぐ進むための次のノードとなる。
"""
import sys
sys.setrecursionlimit(2000000)
input = sys.stdin.readline
N = int(input())
edges = [{} for _ in range(N)]
#dpでiからjへの最短コストを管理する。
for _ in range(N-1):
    a,b,c = map(int,input().split())
    edges[a-1][b]=c
    edges[b-1][a]=c

Q,K = map(int,input().split())
dp = [float("INF")]*(N)

path = {}
def dfs(i,c):
    dp[i-1]=c
    path[i]=""
    for n,cost in edges[i-1].items():
        if n not in path:
            dfs(n, c + cost)

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

Submission status: Time Limit Exceeded

Solution code:
import heapq

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
visited = set()
h = [(0, K, -1)]
while h:
    d0, node, parent = heapq.heappop(h)
    if node in visited:
        continue
    visited.add(node)
    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])

Submission status: Time Limit Exceeded

Solution code:
import heapq

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 = [10 ** 10] * N
visited = set()
h = [(0, K, -1)]
while h:
    d0, node, parent = heapq.heappop(h)
    if node in visited:
        continue
    visited.add(node)
    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])

Submission status: Time Limit Exceeded

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(x, y):
    seen = set()
    d = 0
    stack = deque([[tree[x], d]])
    flag = True
    while flag:
        connect, d = stack.popleft()
        for i in connect:
            if i[0] not in seen:
                seen.add(i[0])
                d += i[1]
                if i[0] == y:
                    flag = False
                    break
                stack.append([tree[i[0]], d])
                d -= i[1]
    return d

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

Submission status: Time Limit Exceeded

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(x, y):
    seen = set()
    d = 0
    stack = deque([[tree[x], d]])
    flag = True
    while flag:
        connect, d = stack.popleft()
        for i in connect:
            if i[0] not in seen:
                seen.add(i[0])
                d += i[1]
                if i[0] == y:
                    flag = False
                    break
                stack.append([tree[i[0]], d])
                d -= i[1]
    return d

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

Submission status: Time Limit Exceeded

Solution code:
import queue
import sys
sys.setrecursionlimit(10**7)
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

def dfs(p):
    for i in range(len(abc[p])):
        num = abc[p][i][0]
        if path[num] != -1:
            continue
        else:
            path[num] = path[p] + abc[p][i][1]
            dfs(num)

dfs(k)

for i in range(Q):
    print(path[xy[i][0]]+path[xy[i][1]])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N = int(input())
graph = [[] for _ in range(N+1)] #木構造を入れておく
long = [0] * (N+1) #Kから任意のノードまでの距離

for i in range(N-1):
  x, y, z = map(int, input().split())
  graph[x].append([y, z])
  graph[y].append([x, z])
  
Q, K = map(int, input().split())
x = list()
y = list()
  
for i in range(1,N+1): #Kから任意のノードまでの距離を求める
  q = deque([K])
  while q:
    t = q.popleft()
    for i in range(len(graph[t])):
      next_t = graph[t][i][0]
      if(long[next_t] > 0):
        continue
        
      else:
        q.append(next_t)
        long[next_t] = long[t] + graph[t][i][1]
        

for i in range(Q):
  x_i, y_i = map(int, input().split())
  ans = long[x_i] + long[y_i]
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N = int(input())
graph = [[] for _ in range(N+1)] #木構造を入れておく
long = [0] * (N+1) #Kから任意のノードまでの距離

for i in range(N-1):
  x, y, z = map(int, input().split())
  graph[x].append([y, z])
  graph[y].append([x, z])
  
Q, K = map(int, input().split())
x = [0] * Q
y = [0] * Q

for i in range(Q):
  x_i, y_i = map(int, input().split())
  x[i] = x_i
  y[i] = y_i
  
for i in range(1,N+1): #Kから任意のノードまでの距離を求める
  q = deque([K])
  while q:
    t = q.popleft()
    tlen = len(graph[t])
    for i in range(tlen):
      next_t = graph[t][i][0]
      if(long[next_t] > 0):
        continue
      q.append(next_t)
      long[next_t] = long[t] + graph[t][i][1]
        

for i in range(Q):
  print(long[x[i]] + long[y[i]])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N = int(input())
graph = [[] for _ in range(N+1)] #木構造を入れておく
long = [0] * (N+1) #Kから任意のノードまでの距離

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

for i in range(Q):
  x_i, y_i = map(int, input().split())
  x.append(x_i)
  y.append(y_i)

  
for i in range(1,N+1): #Kから任意のノードまでの距離を求める
  q = deque([K])
  while q:
    t = q.popleft()
    for i in range(len(graph[t])):
      next_t = graph[t][i][0]
      if(long[next_t] > 0):
        continue
        
      else:
        q.append(next_t)
        long[next_t] = long[t] + graph[t][i][1]
        

for i in range(Q):
  ans = long[x[i]] + long[y[i]]
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N = int(input())
graph = [[] for _ in range(N+1)] #木構造を入れておく
long = [0] * (N+1) #Kから任意のノードまでの距離

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

for i in range(Q):
  x_i, y_i = map(int, input().split())
  x.append(x_i)
  y.append(y_i)

  
for i in range(1,N+1): #Kから任意のノードまでの距離を求める
  q = deque([K])
  while q:
    t = q.popleft()
    for i in range(len(graph[t])):
      next_t = graph[t][i][0]
      if(long[next_t] > 0):
        continue
        
      else:
        q.append(next_t)
        long[next_t] = long[t] + graph[t][i][1]
        

for i in range(Q):
  ans = long[x[i]] + long[y[i]]
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import csgraph_from_dense, shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

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

ma = [[0]*n for _ in range(n)]
for a, b, c in list_ABC:
    ma[a-1][b-1] = c
    ma[b-1][a-1] = c

a = csgraph_from_dense(ma, null_value=0)
b = dijkstra(a, indices=k-1 , directed=False).astype(int)

for x, y in list_XY:
    print(b[x-1]+b[y-1])

Submission status: Time Limit Exceeded

Solution code:
def dijkstra(s, n, w, cost):
    # 始点sから各頂点への最短距離
    # n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0

    while True:
        v = -1
        # まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
                v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
            break
        used[v] = True

        for j in range(n):
            d[j] = min(d[j], d[v] + cost[v][j])
    return d


################################
n = int(input())  # n:頂点数　w:辺の数
w = n - 1
cost = [[float("inf") for i in range(n)] for i in range(n)]
# cost[u][v] : 辺uvのコスト(存在しないときはinf この場合は10**10)
for i in range(w):
    x, y, z = map(int, input().split())
    cost[x-1][y-1] = z
    cost[y-1][x-1] = z

q, k = map(int, input().split())
list_XY = [ list(map(int,input().split(" "))) for i in range(q)]

ans = dijkstra(k-1, n, w, cost)

for x, y in list_XY:
    print(ans[x-1]+ans[y-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

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

ma = [[0]*n for _ in range(n)]
for a, b, c in list_ABC:
    ma[a-1][b-1] = c
    ma[b-1][a-1] = c

a = csr_matrix(ma)
b = dijkstra(a, indices=k-1 , directed=False).astype(int)

for x, y in list_XY:
    print(b[x-1]+b[y-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

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

ma = [[0]*n for _ in range(n)]
for a, b, c in list_ABC:
    ma[a-1][b-1] = c
    ma[b-1][a-1] = c

a = csr_matrix(ma)
b = dijkstra(a, directed=True).astype(int)

for x, y in list_XY:
    print(b[x-1,k-1]+b[k-1,y-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

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

ma = [[0]*n for _ in range(n)]
for a, b, c in list_ABC:
    ma[a-1][b-1] = c
    ma[b-1][a-1] = c

a = csr_matrix(ma)
b = dijkstra(a, directed=False).astype(int)

for x, y in list_XY:
    print(b[x-1,k-1]+b[k-1,y-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

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

ma = [[0]*n for _ in range(n)]
for a, b, c in list_ABC:
    ma[a-1][b-1] = c
    ma[b-1][a-1] = c

a = csr_matrix(ma)
b = dijkstra(a, directed=False).astype(int)

for x, y in list_XY:
    print(b[x-1, k-1]+b[k-1, y-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

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

ma = [[0]*n for _ in range(n)]
for a, b, c in list_ABC:
    ma[a-1][b-1] = c
    ma[b-1][a-1] = c

a = csr_matrix(ma)
b = dijkstra(a, directed=False).astype(int)

for x, y in list_XY:
    print(b[x-1][k-1]+b[k-1][y-1])

Submission status: Time Limit Exceeded

Solution code:
# Bellman-Ford

def shortest_path(s,n,es):
    # s : 始点、　n : 頂点数、 w : 辺の数、 es[i] : 辺の始点、辺の終点、辺のコスト
    # dはsからの最短距離を表す(最初は始点以外はINFに設定しておく)
    d = [float('inf')] * n
    d[s] = 0

    # 無限ループ(速さを求めるならn-1回for文を回す)
    while True:
        # 無限ループの終了条件は1度も最短距離が更新されなかったとき
        update = False
        # 全ての辺に対して最短距離を緩和していく
        for p,q,r in es:
            # 点p→qに対して最短距離を更新する
            if d[p] != float('inf') and d[q] > d[p] + r:
                d[q] = d[p] + r
                update = True
        if not update:
            break
    return d


# n,w = map(int, input().split())
n = int(input())
es = []

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

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

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

d_list = shortest_path(k-1, n, es)

for i, j in QQ:
    print(d_list[i] + d_list[j])

Submission status: Time Limit Exceeded

Solution code:
def dijkstra(s,n,w,cost):
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    while True:
        v = -1
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d

N = int(input())
cost = [[float("inf") for i in range(N)] for i in range(N)]
for _ in range(N-1):
    x,y,z = map(int,input().split())
    cost[x-1][y-1] = z
    cost[y-1][x-1] = z
Q, K = map(int, input().split())
result = dijkstra(K-1,N,N-1,cost)
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: Time Limit Exceeded

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)]
cost = [[-1]*n for i in range(n)]
for a,b,c in abc:
    a,b = a-1,b-1
    cost[a][b]=c
    cost[b][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):

    if dist[v]==-1:
        dist[v] = dist[parent] + cost[v][parent]
    for i,d in enumerate(cost[v]):
        if d!=-1 and dist[i]==-1:
            dfs(i,v)

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

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