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

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()) # 頂点数
W = N - 1 # 辺の数

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

K_costs = dijkstra(K - 1, N, W, cost) # Kから各頂点へのコスト
ans = [] # クエリごとの答え

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

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
def dijkstra(s, n, cost):
    d = [float("inf")] * (n+1)
    used = [False] * (n+1)
    d[s] = 0

    while True:
        v = -1
        for i in range(1, n+1):
            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(1, n+1):
            d[j] = min(d[j], d[v] + cost[v][j])
    return d


n = int(input())
inf = float("inf")
cost = [[inf]*(n+1) for _ in range(n+1)]
for _ in range(n-1):
    a, b, c = map(int, input().split())
    cost[a][b] = c
    cost[b][a] = c
q, k = map(int, input().split())
ans = dijkstra(k, n, cost)
for _ in range(q):
    x, y = map(int, input().split())
    print(ans[x] + ans[y])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 7)


def dfs(v, parent, d):
    depth[v] = d
    for to, cost in tree[v]:
        if to == parent:
            continue
        dfs(to, v, d + cost)


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

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

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

from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
from scipy.sparse import csr_matrix

arr = [[0 for i in range(n)] for j in range(n)]
for a in abc:
    arr[a[0]-1][a[1]-1] = a[2]
    arr[a[1]-1][a[0]-1] = a[2]

dist = dijkstra(csr_matrix(arr),indices=[k-1])

for tmp in que:
    print(int(dist[0][tmp[0]-1] + dist[0][tmp[1]-1]))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


class PriorityQueue:
    def __init__(self, l=[]):
        self.__q = l
        heapq.heapify(self.__q)
        return

    def push(self, n):
        heapq.heappush(self.__q, n)
        return

    def pop(self):
        return heapq.heappop(self.__q)


sys.setrecursionlimit(1000000)
MOD = int(1e09) + 7
INF = int(1e15)


def bfs(s, g, N, G):
    if s == g:
        return 0
    q = []
    q.append(s)
    memo = [0 for _ in range(N)]
    while q != []:
        i = q.pop()
        if i == g:
            return memo[i]
        for n in G[i]:
            if memo[n[0]] != 0:
                continue
            memo[n[0]] = memo[i] + n[1]
            q.append(n[0])
    return 0


def main():
    # sys.stdin = open("Sample.txt")
    N = Scanner.int()
    G = [[] for _ in range(N)]
    for i in range(N - 1):
        a, b, c = Scanner.map_int()
        a -= 1
        b -= 1
        G[a].append((b, c))
        G[b].append((a, c))
    Q, K = Scanner.map_int()
    K -= 1
    length = [0] * N
    for i in range(N):
        length[i] = bfs(i, K, N, G)
    query = Scanner.int_list_list(Q)
    for q in query:
        print(length[q[0] - 1] + length[q[1] - 1])
    return


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, csgraph_from_dense

input = sys.stdin.readline


def main():
    N = int(input())
    edge = [[0] * N for j in range(N)]
    for _ in range(N - 1):
        a, b, c = [int(x) for x in input().split()]
        edge[a - 1][b - 1] = c
        edge[b - 1][a - 1] = c

    G = csgraph_from_dense(edge, null_value=0)
    d = johnson(G)

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, csgraph_from_dense

input = sys.stdin.readline


def main():
    N = int(input())
    edge = [[0] * N for j in range(N)]
    for _ in range(N - 1):
        a, b, c = [int(x) for x in input().split()]
        edge[a - 1][b - 1] = c
        edge[b - 1][a - 1] = c

    G = csgraph_from_dense(edge, null_value=0)
    d = bellman_ford(G)

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, csgraph_from_dense

input = sys.stdin.readline


def main():
    N = int(input())
    edge = [[0] * N for j in range(N)]
    for _ in range(N - 1):
        a, b, c = [int(x) for x in input().split()]
        edge[a - 1][b - 1] = c
        edge[b - 1][a - 1] = c

    G = csgraph_from_dense(edge, null_value=0)
    d = dijkstra(G)

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, csgraph_from_dense

input = sys.stdin.readline


def main():
    N = int(input())
    edge = [[0] * N for j in range(N)]
    for _ in range(N - 1):
        a, b, c = [int(x) for x in input().split()]
        edge[a - 1][b - 1] = c
        edge[b - 1][a - 1] = c

    G = csgraph_from_dense(edge, null_value=0)
    d = floyd_warshall(G)

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, csgraph_from_dense

input = sys.stdin.readline


def main():
    N = int(input())
    edge = [[10 ** 9 + 1] * N for j in range(N)]
    for _ in range(N - 1):
        a, b, c = [int(x) for x in input().split()]
        edge[a - 1][b - 1] = c
        edge[b - 1][a - 1] = c

    G = csgraph_from_dense(edge, null_value=10 ** 9 + 1)
    d = floyd_warshall(G)

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, csgraph_from_dense
# [[10 ** 9, 1, 2],
#  [3, 10 ** 9, 2]
#  [10 ** 9, 4, 7]]


input = sys.stdin.readline


def main():
    N = int(input())
    ABC = [[int(x) for x in input().split()] for _ in range(N - 1)]

    edge = [[10 ** 9 + 1] * N for j in range(N)]
    for a, b, c in ABC:
        edge[a - 1][b - 1] = c
        edge[b - 1][a - 1] = c

    G = csgraph_from_dense(edge, null_value=10 ** 9 + 1)
    d = floyd_warshall(G)

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def dijkstra(s: int, n: int, w: int, cost: list) -> list:
    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())
t = [[float("inf")]*(n) for _ in range(n)]
for _ in range(n-1):
    a, b, c = map(int, input().split())
    t[a-1][b-1] = c
    t[b-1][a-1] = c

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

for _ 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())
g = [[0] * (N+1) for x in range(N+1)]
for i in range(N - 1):
  (a, b, c) = map(int, input().split())
  g[a][b] = g[b][a] = c

(Q, K) = map(int, input().split())
d = [-1] * (N+1)
d[K] = 0

def fill(i):
  if(d[i] == -1):
    return
  for j in range(1, N+1):
    if(g[i][j] != 0 and d[j] == -1):
      d[j] = d[i] + g[i][j]
      fill(j)
  return
  
fill(K)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

INF = 10**18

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


def warshall_floyd(dist):
    for k, _ in enumerate(dist):
        for i, _ in enumerate(dist):
            for j, _ in enumerate(dist):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist


dist = [[INF] * (N + 1) for _ in range(N + 1)]
for abc in ABC:
    dist[abc[0] - 1][abc[1] - 1] = abc[2]
    dist[abc[1] - 1][abc[0] - 1] = abc[2]

dist = warshall_floyd(dist)

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000000)
INF = 1<<32


def solve(N: int, a: "List[int]", b: "List[int]", c: "List[int]", Q: int, K: int, x: "List[int]", y: "List[int]"):
    """
    Warshall-Floyd
    input:  c[|V|][|V|]
            input example to from cost
            (c[i][i] == 0)
    Output: Minimun cost of all paths in the inputed graph 
    """
    V = N
    INF = 1<<64

    g = [[INF] * (N+1) for i in range(N+1)]
    for i in range(1, N+1):
        g[i][i] = 0
    for i in range(N-1):
        g[a[i]][b[i]] = c[i]
        g[b[i]][a[i]] = c[i]
    
    for k in range(V+1):
        for i in range(V+1):
            if g[i][k] == INF : continue
            for j in range(V+1):
                if g[k][j] == INF: continue
                g[i][j] = min(g[i][j], g[i][k]+g[k][j])

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

    # for i in g:
    #     print(i)

    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N - 1)  # type: "List[int]"
    b = [int()] * (N - 1)  # type: "List[int]"
    c = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
    Q = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    x = [int()] * (Q)  # type: "List[int]"
    y = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, a, b, c, Q, K, x, y)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N = int(input())
graph = [[] * N for _ in range(N)]
graph_dist = [[0] * N for _ in range(N)]
C = [0] * (N - 1)
for i in range(N-1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
    graph_dist[a][b] = c
    graph_dist[b][a] = c

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

# BFSのためのデータ構造
dist = [-1 for _ in range(N)]   # 全頂点を未訪問に
que = deque()

# 初期条件(頂点 K-1 を初期ノードとする)
dist[K-1] = 0
que.append(K-1)

# BFS 開始(キューが空になるまで探索を行う)
while que:
    v = que[0]
    que.popleft()
    for new_v in graph[v]:
        if dist[new_v] != -1:   # すでに探索済みの頂点は探索しない
            continue
        # 新たな頂点 new_vについて距離情報を更新してキューに追加する
        dist[new_v] = dist[v] + graph_dist[v][new_v]
        que.append(new_v)


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

Submission status: Time Limit Exceeded

Solution code:
def dijkstra(s: int, n: int, w: int, cost: list) -> list:
    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())
t = [[float("inf")]*(n) for _ in range(n)]
for _ in range(n-1):
    a, b, c = map(int, input().split())
    t[a-1][b-1] = c
    t[b-1][a-1] = c

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

for _ 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())
edge = [[] for i in range(N)]
for i in range(N-1):
    a, b, c = map(int, input().split())
    edge[a-1].append([c, b-1])
    edge[b-1].append([c, a-1])
Q, K = map(int, input().split())
query = [list(map(int, input().split())) for _ in range(Q)]

import heapq

def dijkstra_heap(s):
    d = [float('inf')] * N
    used = [False] * N
    d[s] = 0
    used[s] = True
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist, e)
    while len(edgelist):
        min_edge = heapq.heappop(edgelist)
        if used[min_edge[1]]:
            continue
        v = min_edge[1]
        d[v] = min_edge[0]
        used[v] = True
        for e in edge[v]:
            heapq.heappush(edgelist, [e[0] + d[v], e[1]])
    return d

dist = dijkstra_heap(K-1)
for q in query:
    x, y = q[0], q[1]
    x -= 1
    y -= 1
    print(dist[x] + dist[y])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
edge = [[] for i in range(N)]
for i in range(N-1):
    a, b, c = map(int, input().split())
    edge[a-1].append([c, b-1])
    edge[b-1].append([c, a-1])
Q, K = map(int, input().split())
query = [list(map(int, input().split())) for _ in range(Q)]

import heapq

def dijkstra_heap(s):
    d = [float('inf')] * N
    used = [False] * N
    d[s] = 0
    used[s] = True
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist, e)
    while len(edgelist):
        min_edge = heapq.heappop(edgelist)
        if used[min_edge[1]]:
            continue
        v = min_edge[1]
        d[v] = min_edge[0]
        used[v] = True
        for e in edge[v]:
            heapq.heappush(edgelist, [e[0] + d[v], e[1]])
    return d

for q in query:
    x, y = q[0], q[1]
    x -= 1
    y -= 1
    dist = dijkstra_heap(K-1)
    print(dist[x] + dist[y])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
N=int(input())
tree=np.array([[0]*N for i in range(N)])
for i in range(N-1):
    a,b,c=map(int,input().split(' '))
    tree[a-1][b-1] = c
    tree[b-1][a-1] = c
Q,K=map(int,input().split(' '))
ans = dijkstra(tree,indices=K-1)
for i in range(Q):
    s,e=map(int,input().split(' '))
    print(int(ans[s-1]+ans[e-1]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
N=int(input())
tree=[[0]*N for i in range(N)]
for i in range(N-1):
    a,b,c=map(int,input().split(' '))
    tree[a-1][b-1] = c
    tree[b-1][a-1] = c
tree = np.array(tree)
Q,K=map(int,input().split(' '))
ans = dijkstra(tree,indices=K-1)
for i in range(Q):
    s,e=map(int,input().split(' '))
    print(int(ans[s-1]+ans[e-1]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
import math
N=int(input())
tree=[[0]*N for i in range(N)]
for i in range(N-1):
    a,b,c=map(int,input().split(' '))
    tree[a-1][b-1] = c
    tree[b-1][a-1] = c
tree = np.array(tree)
Q,K=map(int,input().split(' '))
csr = csr_matrix(tree)
ans = dijkstra(csr,indices=K-1)
for i in range(Q):
    s,e=map(int,input().split(' '))
    print(int(ans[s-1]+ans[e-1]))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
n = int(input())
m = [[-1 for _ in range(n)] for _ in range(n)]
np = [deque([]) for _ in range(n)]
for _ in range(n-1):
    a, b, c = [int(x) for x in input().strip().split()]
    m[a-1][b-1] = c
    m[b-1][a-1] = c
    np[a-1].append(b)
    np[b-1].append(a)

q, k = [int(x) for x in input().strip().split()]
master = [-1 for _ in range(n)]
master[k-1] = 0

def dfs(cur, pre, master):
    #print('cur = {}, pre = {}'.format(cur, pre))
    for p in np[cur-1]:
        if p == pre:
            continue
        master[p-1] = master[cur-1] + m[cur-1][p-1]
        dfs(p, cur, master)

dfs(k, -1, master)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
m = [[-1 for _ in range(n)] for _ in range(n)]
np = [[] for _ in range(n)]
for _ in range(n-1):
    a, b, c = [int(x) for x in input().strip().split()]
    m[a-1][b-1] = c
    m[b-1][a-1] = c
    np[a-1].append(b)
    np[b-1].append(a)

q, k = [int(x) for x in input().strip().split()]
master = [-1 for _ in range(n)]
master[k-1] = 0

def dfs(cur, pre, master):
    #print('cur = {}, pre = {}'.format(cur, pre))
    for p in np[cur-1]:
        if p == pre:
            continue
        master[p-1] = master[cur-1] + m[cur-1][p-1]
        dfs(p, cur, master)

dfs(k, -1, master)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict, deque
import bisect
from heapq import *
from math import factorial
sys.setrecursionlimit(200000)
input = sys.stdin.readline

N, = map(int, input().split())
# N = int(input())
# L = [int(v) for v in input().split()]
# L = [[int(v) for v in input().split()] for _ in range(N)]
# L = [int(input()) for _ in range(N)]
# L = [list(input().strip())  for _ in range(N)]
# S = input().strip()

L = [[int(v) for v in input().split()] for _ in range(N - 1)]
Q, K = map(int, input().split())
QL = [[int(v) for v in input().split()] for _ in range(Q)]

m = {}
for a, b, c in L:
    if m.get(a) == None:
        m[a] = {}
    if m.get(b) == None:
        m[b] = {}

    m[a][b] = c
    m[b][a] = c

def dfs(now, a, l, al):
    ans = 10 ** 18
    if now == a:
        return l
    for k, v in m[now].items():
        if k in al:
            continue
        re = dfs(k, a, l + v, al + [k])
        ans = min(ans, re)
    return ans

for i in range(N):
    a = dfs(K, i + 1, 0, [])
    m[K][i + 1] = a

for x, y in QL:
    print(m[K][x] + m[K][y])

Submission status: Time Limit Exceeded

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

def dfs(v, d=0):
    seen[v] = True
    dist[v] = d

    for i in graph[v]:
        next_v = i[0]
        l = i[1]
        if seen[next_v] == True:
            continue
        dfs(next_v, d+l)

    return

N = int(input())

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

for i 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())

for i in range(Q):
    ans = 0
    x, y = map(int, input().split())

    seen = [False for i in range(N + 1)]
    dist = [0 for i in range(N + 1)]
    dfs(x)
    ans += dist[K]

    seen = [False for i in range(N + 1)]
    dist = [0 for i in range(N + 1)]
    dfs(K)
    ans += dist[y]
    
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())

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

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

Q,K=map(int,input().split())
C=[0]*N
stack=[]
for i in range(N):
    if i==K-1:
        C[i]=0
    else:
        chk = [0] * N
        stack=[[K-1,i,0]]
        f=True
        while stack:
            if f==False:
                break
            s,g,d=stack.pop()
            chk[s]=1
            for j,c in R[s]:
                if chk[j]==1:continue
                if j==g:
                    C[i]=d+c
                    f=False
                    break
                else:
                    stack.append([j,g,d+c])

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

Submission status: Time Limit Exceeded

Solution code:
N=int(input())

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

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

Q,K=map(int,input().split())
C=[0]*N
stack=[]
for i in range(N):
    if i==K-1:
        C[i]=0
    else:
        chk = [0] * N
        stack=[[K-1,i,0]]
        while stack:
            s,g,d=stack.pop()
            chk[s]=1
            for j,c in R[s]:
                if chk[j]==1:continue
                if j==g:
                    C[i]=d+c
                    break
                else:
                    stack.append([j,g,d+c])

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ki = [[] for _ in range(n)]
dlist = [[0]*n for _ in range(n)]
dist = [0]*n
for i in range(n-1):
    a,b,c  = map(int,input().split())
    a -= 1
    b -= 1
    ki[a].append(b)
    ki[b].append(a)
    dlist[a][b] = dlist[b][a] = c
q,k = map(int,input().split())
k -= 1
def dfs(now,last = -1):
    for next in ki[now]:
        if next == last:continue
        dist[next] = dist[now] + dlist[now][next]
        dfs(next,now)
dfs(k)
for i in range(q):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    print(dist[x]+dist[y])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from heapq import heappop, heappush
 
class Graph:
 
    def __init__(self):
        self.graph = defaultdict(list)
        self.vertices = set()
        self.edges = []
 
    def add_edge(self, a, b, weight=1):
        self.graph[a].append((b, weight))
        self.vertices |= {a, b}
        self.edges.append((a, b, weight))

        self.graph[b].append((a, weight))
        self.edges.append((b, a, weight))
 
    def get_vertices(self):
        return sorted(list(self.vertices))
 
    def num_of_vertices(self):
        return len(self.vertices)
 
    def get_edges(self):
        return self.edges
 
    def num_of_edges(self):
        return len(self.edges)
 
class Dijkstra:
 
    def __init__(self, graph, start):
        self.g = graph.graph
 
        self.dist = defaultdict(lambda: float("inf"))
        self.dist[start] = 0
 
        self.prev = defaultdict(lambda: None)
 
        self.Q = []
        heappush(self.Q, (0, 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):
 
        return self.dist[goal]
 
    def shortest_path(self, goal):
 
        path = []
        vertice = goal
        while vertice is not None:
            path.append(vertice)
            vertice = self.prev[vertice]
 
        return path[::-1]

G = Graph()
N = int(input())
for i in range(N-1):
    a, b, c = map(int, input().split())
    G.add_edge(a, b, c)

Q, K = map(int, input().split())
for _ in range(Q):
    x, y = map(int, input().split())
    D1 = Dijkstra(G, x)
    D2 = Dijkstra(G, K)
    print(D1.shortest_distance(K)+D2.shortest_distance(y))