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
sys.setrecursionlimit(100000)

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

tree = [{} for _ in range(N)]
for a, b, c in ABC:
	a, b = a - 1, b - 1
	tree[a][b] = c
	tree[b][a] = c

costs = {}
def dfs(current, cost):
	global costs
	costs[current] = cost
	for n in tree[current]:
		if n in costs:
			continue
		dfs(n, cost + tree[current][n])

dfs(K - 1, 0)

for x, y in XY:
	x, y = x - 1, y - 1
	print(costs[x] + costs[y])

#print(tree)
#print(costs)

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

N = I()
abc = LIR(N-1)
Q, K = LI()
xy = LIR(Q)

abc = list(map(lambda x: [x[0]-1, x[1]-1, x[2]], abc))
xy = list(map(lambda x: [x[0]-1, x[1]-1], xy))
K = K-1

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

edge = [[0]*N for i in range(N)]
for a, b, c in abc:
    edge[a][b] = c
    edge[b][a] = c
    utov[a].append(b)
    utov[b].append(a)

bfs_map = [-1]*N

q = deque()
q.append(K)
bfs_map[K] = 0

while q:
    u = q.popleft()
    for v in utov[u]:
        if (bfs_map[v] == -1) or (bfs_map[v] > bfs_map[u]+edge[u][v]):
            bfs_map[v] = bfs_map[u]+edge[u][v]
            q.append(v)

for x, y in xy:
    print(bfs_map[x]+bfs_map[y])

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
"""
def gcd(a,b):
    if a == 0:
        return b
    return gcd(b%a,a)
n = I()
a = IR(n)
l = a[0]
for i in range(1,n):
    g = gcd(l,a[i])
    l *= a[i]//g
print(l)
"""

#B
import queue
n = I()
v = [[] for i in range(n)]
for i in range(n-1):
    a,b,c = LI()
    a -= 1
    b -= 1
    v[a].append([b,c])
    v[b].append([a,c])
Q,k = LI()
d = [-1 for i in range(n)]
d[k-1] = 0
q = queue.Queue()
q.put(k-1)
while q:
    x = q.get()
    for y,c in v[x]:
        if d[y] == -1:
            d[y] = d[x]+c
            q.put(y)
for i in range(Q):
    x,y = LI()
    x -= 1
    y -= 1
    print(d[x]+d[y])
#C

#D

#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Time Limit Exceeded

Solution code:
def solve(n, a, b, c, q, k, x, y):
    E = {}
    G = {}
    for u, v, d in zip(a, b, c):
        if not u in E:
            E[u] = []
        if not v in E:
            E[v] = []
        E[u].append(v)
        E[v].append(u)
        G[u, v] = d
        G[v, u] = d
    dist = {}
    dist[k] = 0
    que = [k]
    group = {}
    while que:
        v = que.pop(0)
        for u in E[v]:
            if not u in dist:
                dist[u] = dist[v] + G[u,v]
                if v == k:
                    group[u] = u
                else:
                    group[u] = group[v]
                que.append(u)
    for i in range(q):
        if group[x[i]] == group[y[i]]:
            print(dist[x[i]] + dist[y[i]])
        else:
            print(dist[x[i]] + dist[y[i]])

n = int(input())
a = [0] * (n-1)
b = [0] * (n-1)
c = [0] * (n-1)
for i in range(n-1):
    a[i], b[i], c[i] = map(int, input().split())
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())
solve(n, a, b, c, q, k, x, y)

Submission status: Time Limit Exceeded

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

import sys
sys.setrecursionlimit(N+10)
def bfs(Q,memo,current,Nei):
    for e in Nei[current]:
        if memo[e] == float('inf'):
            Q.append(e)
            memo[e] = memo[current] + edge[(current,e)]
    if len(Q) == 0:
        return memo
    else:
        next = Q.pop(0)
        return bfs(Q,memo,next,Nei)
queue = []
memo = [float('inf')]*(N+1)
memo[K] = 0
Ans = bfs(queue,memo,K,neighbor)

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N = int(input())

T = [[] for i in range(N)]
for i in range(N-1) :
    u,v,c = map(int,input().split())
    u -= 1
    v -= 1
    T[u].append([v,c])
    T[v].append([u,c])

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

L = []

for i in range(Q) :
    u,v = map(int,input().split())
    u -= 1
    v -= 1
    L.append([u,v])

dist = [0]*N

q = deque([[K,0]])

explored = [0]*N

C = []
while q :
    now,c = q.pop()
    
    if not explored[now] :
        C.append(c)
        dist[now] = sum(C)
        explored[now] = 1
    
    flg = 1
    
    while T[now] :
        to, c = T[now].pop(0)
        if explored[to] :
            continue
        
        q.append([now, 0])
        q.append([to, c])
        flg = 0
        break
    if flg :
        if len(T[now]) == 0 :
            C.pop(-1)
    
    #print("now:", now, "C:", C)
        
ans = []

for i in range(Q) :
    u,v = L[i]
    calc = dist[u] + dist[v]
    ans.append(calc)

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
d = [[0 for i in range(N+1)] for j in range(N+1)]
for i in range(N-1):
    a,b,c = map(int,input().split())
    d[a][b] = c
    d[b][a] = c
Q,K = map(int,input().split())
#p is parent
#pcd is parent-child distance
reached = [0 for i in range(N+1)]
def f(p,pcd):
    global d,K,reached
    reached[p] = 1
    d[K][p] = pcd
    for c in range(N+1):
        if d[p][c]>0 and reached[c] == 0:
            f(c,pcd+d[p][c])
f(K,0)
for i in range(Q):
    x,y = map(int,input().split())
    print(d[K][x]+d[K][y])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
v = [[]for i in range(N+1)]
d = [[0 for i in range(N+1)] for j in range(N+1)]
for i in range(N-1):
    a,b,c = map(int,input().split())
    v[a].append(b)
    v[b].append(a)
    d[a][b] = c
    d[b][a] = c
Q,K = map(int,input().split())
#p is parent
#pcd is parent-child distance
reached = [0 for i in range(N+1)]
def f(p,pcd):
    global v,d,K,reached
    reached[p] = 1
    d[K][p] = pcd
    for c in v[p]:
        if reached[c] == 0:
            f(c,pcd+d[p][c])
f(K,0)
for i in range(Q):
    x,y = map(int,input().split())
    print(d[K][x]+d[K][y])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
sys.setrecursionlimit(1000000)

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

graph = defaultdict(set)
for v, w, c in edges:
    graph[v].add((w, c))
    graph[w].add((v, c))

INF = 10 ** 9 + 7
dp = [INF] * (N + 1)
visited = [False] * (N + 1)

def dfs(v, p, d):    
    dp[v] = d
    visited[v] = True
    for j, c in graph[v]:
        if j == p or visited[j]:
            continue
        dfs(j, v, d + c)

dfs(K, 0, 0)

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

Submission status: Time Limit Exceeded

Solution code:
import heapq

def dijkstra(graph, node, start):
    dist = [float("inf") for _ in range(node)]

    dist[start] = 0
    q = []
    heapq.heappush(q, (0, start))

    while q:
        cost, cur_node = heapq.heappop(q)

        if dist[cur_node] < cost:
            continue

        for nex_cost, nex_node in graph[cur_node]:
            dist_cand = dist[cur_node] + nex_cost
            if dist_cand < dist[nex_node]:
                dist[nex_node] = dist_cand
                heapq.heappush(q, (dist[nex_node], nex_node))

    return dist


n = int(input())
adj = [[] for _ in range(n)]
for i in range(n - 1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    adj[a].append((c, b))
    adj[b].append((c, a))
q, k = map(int, input().split())
k -= 1
shortest = []
for i in range(n):
    shortest.append(dijkstra(adj, n, i))
for i in range(q):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    print(shortest[x][k] + shortest[y][k])

Submission status: Time Limit Exceeded

Solution code:
# KからDFS -> xからKまでとyからKまで

import sys
sys.setrecursionlimit(10**8)

n = int(input())
graph = [[] for _ in range(n)]
costs = [0 for _ in range(n)]

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

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


def dfs(cur, cost):
    for g in graph[cur]:
        if g[0] != k-1 and costs[g[0]] == 0:
            costs[g[0]] = g[1] + cost
            dfs(g[0], costs[g[0]])


dfs(k - 1, 0)

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys

def warshall_floyd(conn):
    n = len(conn)
    dp = [[v for v in A] for A in conn]
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
    return dp


def solve(N: int, A: "List[int]", B: "List[int]", C: "List[int]", Q: int, K: int, x: "List[int]", y: "List[int]"):

    conn = [[float('inf') for _ in range(N)] for _ in range(N)]
    for i in range(N):
        conn[i][i] = 0
    for j in range(N - 1):
        a = A[j] - 1
        b = B[j] - 1
        conn[a][b] = min(conn[a][b], C[j])
        conn[b][a] = min(conn[b][a], C[j])
    d = warshall_floyd(conn)
    for q in range(Q):
        s = x[q] - 1
        t = y[q] - 1
        k = K - 1
        ret = d[s][k] + d[k][t]
        print(ret)
    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:
import sys
import numpy as np
from scipy.sparse import coo_matrix
from scipy.sparse.csgraph import dijkstra


def main():
    n = int(input())
    U = [0]
    V = [0]
    W = [0]
    for i in range(n-1):
        u, v, w = [int(x) for x in input().split()]
        U.append(u)
        V.append(v)
        W.append(w)
    graph = coo_matrix((W, (U, V)), shape=(n+1, n+1)).tocsr()
    q, k = [int(x) for x in input().split()]
    dist = dijkstra(csgraph=graph, directed=False, indices=k, unweighted=False)
    for j in range(q):
        l, r = [int(x) for x in input().split()]
        print(int(dist[l]+dist[r]))


main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

def warshall_floyd(V, E):
    INF = 10 ** 10
    d = [defaultdict(lambda: INF) for i in range(V)]
    for i, j, c in E:
        d[i - 1][j - 1] = c
        d[j - 1][i - 1] = c
    for k in range(V):
        for i in range(V - 1):
            for j in range(i, V):
                dk = d[i][k] + d[k][j]
                if d[i][j] > dk:
                    d[i][j] = dk
                    d[j][i] = dk
    return d

N = int(input())
E = [list(map(int, input().split())) for _ in range(N - 1)]
d = warshall_floyd(N, E)

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:
import sys

sys.setrecursionlimit(1000000)


def dfs(v, parent, adj, dist):
    for tail, weight in adj[v]:
        if tail == parent:
            continue
        dist[tail] = dist[v] + weight
        dfs(tail, v, adj, dist)


def main():
    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)
    dfs(k, k, adj, dist)
    for j in range(q):
        l, r = [int(x) for x in input().split()]
        print(dist[l] + dist[r])


main()
# print(*data, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(1000000)


def dfs(v, parent):
    for tail, weight in adj[v]:
        if tail == parent:
            continue
        dist[tail] = dist[v] + weight
        dfs(tail, v)


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)
dfs(k, k)
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: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import dijkstra
n = int(input())
mat=[[0]*n for i in range(n)]
for i in range(n-1):
    a, b, c = map(int, input().split())
    mat[a-1][b-1]=c
    mat[b-1][a-1]=c
q, k  = map(int, input().split())
distance = dijkstra(mat, directed = False, indices = [k-1])
for i in range(q):
    x, y = map(int, input().split())
    print(int(distance[0][x-1]+distance[0][y-1]))

Submission status: Time Limit Exceeded

Solution code:
import sys

from scipy.sparse import coo_matrix
from scipy.sparse.csgraph import dijkstra

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

N = int(sys.stdin.readline())
A, B, C = list(zip(*[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)]))

graph = coo_matrix((C, (A, B)), shape=(N + 1, N + 1))
dists = dijkstra(graph.tocsr(), indices=K, directed=False)

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

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
edge=[list(map(int,input().split())) for i in range(N-1)]
INF=10**15
c=[[INF]*N for i in range(N)]
for i,j,w in edge:
    c[i-1][j-1]=w
    c[j-1][i-1]=w
Q,K=map(int, input().split())
xy=[list(map(int,input().split())) for i in range(Q)]
from heapq import heappop,heappush
def dij(c,N,start):
    d=[INF]*N
    d[start]=0
    prev=[-1]*N
    q=[]
    heappush(q,(0,start))
    while len(q)>0:
        u=heappop(q)[1]
        for v in range(N):
            if c[u][v]<INF:
                temp=d[u]+c[u][v]
                if d[v]>temp:
                    d[v]=temp
                    prev[v]=u
                    heappush(q,(d[v],v))
    return d
d=dij(c,N,K-1)
for x,y in xy:
    print(d[x-1]+d[y-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
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: Time Limit Exceeded

Solution code:
from scipy.sparse import csc_matrix
import sys
input = sys.stdin.readline

N = int(input())
ABC = [[int(x) for x in input().split()] for _ in range(N-1)]
row,col,val = zip(*ABC)

edge = csc_matrix((val,(row,col)),(N+1,N+1))

Q,K = map(int,input().split())
 
from scipy.sparse.csgraph import dijkstra
dist = dijkstra(edge,directed = False, indices = K).astype(int)
 
for _ in range(Q):
  x,y = map(int,input().split())
  print(dist[x] + dist[y])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

a = []
for i in range(0,n+1):
  a.append([])

for i in range(n-1):
  x,y,z = map(int,input().split())
  a[x] = a[x] + [[y,z]]
  a[y] = a[y] + [[x,z]]
  
c = [-1]*(n+1)
m,k = map(int,input().split())
q = Queue()
q.put(k)
c[k] = 0

while not q.empty():
  x = q.get()
  c0 = c[x]
  for t in a[x]:
    y = t[0]
    z = t[1]
    if c[y] == -1:
      c[y] = c0 + z
      q.put(y)
for i in range(m):
  x,y = map(int,input().split())
  print(c[x]+c[y])

Submission status: Time Limit Exceeded

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

a = []
for i in range(0,n+1):
  a.append([])

for i in range(n-1):
  x,y,z = map(int,input().split())
  a[x] = a[x] + [[y,z]]
  a[y] = a[y] + [[x,z]]
  
c = [-1]*(n+1)
m,k = map(int,input().split())
q = Queue()
q.put(k)
c[k] = 0

while not q.empty():
  x = q.get()
  for t in a[x]:
    y = t[0]
    z = t[1]
    if c[y] == -1:
      c[y] = c[x] + z
      q.put(y)
for i in range(m):
  x,y = map(int,input().split())
  print(c[x]+c[y])

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse import lil_matrix
import sys
input = sys.stdin.readline

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

edge = edge.tocsc()

Q,K = map(int,input().split())
 
from scipy.sparse.csgraph import dijkstra
dist = dijkstra(edge,directed = False, indices = K).astype(int)
 
for _ in range(Q):
  x,y = map(int,input().split())
  print(dist[x] + dist[y])

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse import lil_matrix
import sys
input = sys.stdin.readline

N = int(input())
edge = lil_matrix((N+1,N+1))
 
for _ in range(N-1):
  a,b,c = map(int,input().split())
  edge[a,b] = c
 
Q,K = map(int,input().split())
 
from scipy.sparse.csgraph import dijkstra
dist = dijkstra(edge,directed = False, indices = K).astype(int)
 
for _ in range(Q):
  x,y = map(int,input().split())
  print(dist[x] + dist[y])

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse import lil_matrix

N = int(input())
edge = lil_matrix((N+1,N+1))

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

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

from scipy.sparse.csgraph import dijkstra
dist = dijkstra(edge,directed = False, indices = K).astype(int)

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

Submission status: Time Limit Exceeded

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))
    
# bellman_ford(edges,num_v,source)
# エッジのリストと超点数、スタート地点をinput
# リターンはスタート地点からの各ノードへの最短距離、負の閉路があれば-1*INT_MAXを返す


import sys
INT_MAX = sys.maxsize # 9223372036854775807

def bellman_ford(edges,num_v,source):

    dist=[INT_MAX] * num_v
    dist[source]=0

    #辺の緩和
    has_negative = False
    for i in range(num_v):
        for edge in edges:
            if edge[0] != INT_MAX and dist[edge[1]] > dist[edge[0]] + edge[2]:
                dist[edge[1]] = dist[edge[0]] + edge[2]
                if i==num_v-1:
                    has_negative = True
    
    if has_negative == False:
        return dist
    
    negative = [False] * num_v
    for i in range(num_v):
        for from_edge, to_edge, cost in edges:
            if dist[from_edge] == INT_MAX:
                continue
            if dist[to_edge] > dist[from_edge] + cost:
                dist[to_edge] = dist[from_edge] + cost
                negative[to_edge] = True
            
            if negative[from_edge] == INT_MAX:
                negative[to_edge] = True
                
    for i, is_negative in enumerate(negative):
        if is_negative:
            dist[i] = -1 * INT_MAX
        
    return dist



edges = ABC[:]
for a,b,c in edges[:]:
    edges.append((b,a,c))


shortest = bellman_ford(edges, N+1, K)
    
question = XY[:]

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

Submission status: Time Limit Exceeded

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))
    
# bellman_ford(edges,num_v,source)
# エッジのリストと超点数、スタート地点をinput
# リターンはスタート地点からの各ノードへの最短距離、負の閉路があれば-1*INT_MAXを返す


import sys
INT_MAX = sys.maxsize # 9223372036854775807

def bellman_ford(edges,num_v,source):

    dist=[INT_MAX] * num_v
    dist[source]=0

    #辺の緩和
    has_negative = False
    for i in range(num_v):
        for edge in edges:
            if edge[0] != INT_MAX and dist[edge[1]] > dist[edge[0]] + edge[2]:
                dist[edge[1]] = dist[edge[0]] + edge[2]
                if i==num_v-1:
                    has_negative = True
    
    if has_negative == False:
        return dist
    
    negative = [False] * num_v
    for i in range(num_v):
        for from_edge, to_edge, cost in edges:
            if dist[from_edge] == INT_MAX:
                continue
            if dist[to_edge] > dist[from_edge] + cost:
                dist[to_edge] = dist[from_edge] + cost
                negative[to_edge] = True
            
            if negative[from_edge] == INT_MAX:
                negative[to_edge] = True
                
    for i, is_negative in enumerate(negative):
        if is_negative:
            dist[i] = -1 * INT_MAX
        
    return dist



edges = ABC[:]
for a,b,c in edges[:]:
    edges.append((b,a,c))


shortest = []

for i in range(0, N+1):
    sub_shortest=bellman_ford(edges, N+1, i)
    shortest.append(sub_shortest)
    #print(sub_shortest)
    
question = XY[:]

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
#import numpy as np
from scipy.sparse import csr_matrix, coo_matrix
from scipy.sparse.csgraph import dijkstra, depth_first_tree

#sys.setrecursionlimit(10000)

N = int(input())

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

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

Q, K = [int(i) for i in input().split()]

graph = coo_matrix((weights, (rows, cols)), shape=(N, N)).tocsr()
d1 = dijkstra(graph, indices = K-1, directed=False)

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

Submission status: Time Limit Exceeded

Solution code:
#import sys
#import numpy as np
from scipy.sparse import csr_matrix, coo_matrix
from scipy.sparse.csgraph import dijkstra, depth_first_tree

#sys.setrecursionlimit(10000)

N = int(input())

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

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

Q, K = [int(i) for i in input().split()]

graph = coo_matrix((weights, (rows, cols)), shape=(N, N)).tocsr()
d1 = dijkstra(graph, indices = K-1, directed=False)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(200000)

n = int(input())
edge = [[[] for i in range(2)] for j in range(n)]
dp = [-1] * n
for i in range(n - 1):
    a, b, c = map(int, input().split())
    edge[a - 1][0].append(b - 1)
    edge[a - 1][1].append(c)
    edge[b - 1][0].append(a - 1)
    edge[b - 1][1].append(c)


def distance(x, prev, d):
    dp[x] = d
    for i, j in zip(edge[x][0], edge[x][1]):
        if i == prev:
            continue
        if dp[i] != -1:
            continue
        distance(i, x, d + j)
    return

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

ans = []
distance(k, -1, 0)
for i in range(q):
    x, y = map(int, input().split())
    ans.append(dp[x - 1] + dp[y - 1])

for i in range(q):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
import queue
N=int(input())
d=[-1 for _ in range(N+1)]
e=[[] for _ in range(N+1)]
for _ in range(N-1):
	a,b,c=map(int,input().split())
	e[a].append([b, c])
	e[b].append([a, c])
Q,K=map(int,input().split())
d[K]=0
q=queue.Queue()
q.put(K)
while not q.empty():
	now=q.get()
	for nx,c in e[now]:
		if d[nx] == -1:
			d[nx] = c+d[now]
			q.put(nx)
for _ in range(Q):
	x,y=map(int,input().split())
	print(d[x]+d[y])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(65536)

N=int(input())
d=[-1 for _ in range(N+1)]
e=[[] for _ in range(N+1)]
for _ in range(N-1):
	a,b,c=map(int,input().split())
	e[a].append([b, c])
	e[b].append([a, c])
Q,K=map(int,input().split())
def bfs(now, dis):
	if d[now] != -1:
		return
	d[now] = dis
	for nxt, cos in e[now]:
		bfs(nxt, dis+cos)
bfs(K, 0)
for _ in range(Q):
	x,y=map(int,input().split())
	print(d[x]+d[y])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

N=int(input())
n=[[]for i in range(N+1)]

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

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

L[K]=0

def dfs(x):
    for i in n[x]:
        if L[i[0]]==-1:
            L[i[0]]=L[x]+i[1]
            dfs(i[0])
dfs(K)
#print(n)
#print(L)

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

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
import math

def main():
    # 文字列の2進数を数値にする
    # '101' → '5'
    # 文字列の頭に'0b'をつけてint()にわたす
    # binary = int('0b'+'101',0)

    # 2進数で立っているbitを数える
    # 101(0x5) → 2
    # cnt_bit = bin(5).count('1')
    
    # N! を求める
    # f = math.factorial(N)

    # N の逆元
    # N_inv = pow(N,MOD-2,MOD)

    # nCr
    # Nの階乗 * rの階乗の逆元 * n-rの階乗の逆元
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    INF = float("inf")

    # 大きな素数
    MOD = 10**9+7
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    N = int(input())
    a = []
    b = []
    c = []
    for i in range(N-1):
        s1,s2,s3 = list(int(_) for _ in input().split())
        a.append(s1-1)
        b.append(s2-1)
        c.append(s3)
    Q,K = list(int(_) for _ in input().split())
    x = []
    y = []
    for i in range(Q):
        s1,s2 = list(int(_) for _ in input().split())
        x.append(s1-1)
        y.append(s2-1)
    d = []
    for i in range(N):
        d_i = list(INF for j in range(N))
        d.append(d_i)
        
    for i in range(N):
        for j in range(N):
            if(i == j):
                d[i][j] = 0
    for i in range(N-1):
        d[a[i]][b[i]] = c[i]
        d[b[i]][a[i]] = c[i]

    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j],d[i][k]+d[k][j])

    for i in range(Q):        
        print(d[x[i]][K-1]+d[K-1][y[i]])
    
if __name__ == '__main__':
    main()