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:
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
import random
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])
def graphm():
    n=inp()
    g=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b,w=inpm()
        a-=1
        b-=1
        g[a].append((b,w))
        g[b].append((a,w))
    return n,g
def dijkstra(s,to,n,g): # sからの最短距離 頂点数n
    s -= 1
    que = []
    d = [10**15 for _ in range(n)]
    d[s] = 0
    heappush( que,(0,s) )
    while len(que)>0:
        p =  heappop(que)
        v = p[1]
        if d[v] < p[0]:
            continue
        for i in range(len(g[v])):
            edge = g[v][i]
            if d[edge[0]] > d[v] + edge[1]:
                d[edge[0]] = d[v] + edge[1]
                heappush( que,(d[edge[0]] , edge[0]) )
    return d[to-1]

def main():
    n,graph = graphm()
    q,k = inpm()
    for _ in range(q):
        x,y = inpm()
        print( dijkstra(x,k,n,graph) + dijkstra(k,y,n,graph) )    

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
import random
from heapq import heappop, heappush
#input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])
def graphm():
    n=inp()
    g=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b,w=inpm()
        a-=1
        b-=1
        g[a].append((b,w))
        g[b].append((a,w))
    return n,g
def dijkstra(s,to,n,g): # sからの最短距離 頂点数n
    s -= 1
    que = []
    d = [10**15 for _ in range(n)]
    d[s] = 0
    heappush( que,(0,s) )
    while len(que)>0:
        p =  heappop(que)
        v = p[1]
        if d[v] < p[0]:
            continue
        for i in range(len(g[v])):
            edge = g[v][i]
            if d[edge[0]] > d[v] + edge[1]:
                d[edge[0]] = d[v] + edge[1]
                heappush( que,(d[edge[0]] , edge[0]) )
    return d[to-1]

def main():
    n,graph = graphm()
    q,k = inpm()
    for _ in range(q):
        x,y = inpm()
        print( dijkstra(x,k,n,graph) + dijkstra(k,y,n,graph) )    

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall

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

li = [[0] * (N) for _ in range(N)]

for a, b, c in abc:
  li[a-1][b-1] = c
  li[b-1][a-1] = c
  
nli = np.array(li)
nnli = np.where(nli == 0, 10**12, nli)

G = csgraph_from_dense(nnli, null_value=10**12)
d = floyd_warshall(G)

for x, y in xy:
  print(int(d[x-1, K-1] + d[K-1, y-1]))

Submission status: Time Limit Exceeded

Solution code:
import collections
import sys
input = sys.stdin.readline
N = int(input())
abc = [map(int, input().split()) for i in range(N-1)]

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

k = [set() for i in range(N)]
g = [[-1]*N for i in range(N)]
for a, b, c in abc:
    g[a-1][b-1] = c
    g[b-1][a-1] = c
    k[a-1].add(b-1)
    k[b-1].add(a-1)
c = [-1]*N
reached = [0]*N
c[K-1] = 0
q = collections.deque([K])
reached[K-1] = 1
while(len(q) > 0):
    x = q.popleft()

    for y in k[x-1]:
        if not reached[y]:
            q.append(y+1)
            c[y] = c[x-1]+g[x-1][y]
            reached[y] = 1
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:
import collections
import sys
input = sys.stdin.readline
N = int(input())
abc = [map(int, input().split()) for i in range(N-1)]

Q, K = map(int, input().split())
xy = [map(int, input().split()) for i in range(Q)]
k = [set() for i in range(N)]
g = [[-1]*N for i in range(N)]
for a, b, c in abc:
    g[a-1][b-1] = c
    g[b-1][a-1] = c
    k[a-1].add(b-1)
    k[b-1].add(a-1)
c = [-1]*N
reached = [0]*N
c[K-1] = 0
q = collections.deque([K])
reached[K-1] = 1
while(len(q) > 0):
    x = q.popleft()

    for y in k[x-1]:
        if not reached[y]:
            q.append(y+1)
            c[y] = c[x-1]+g[x-1][y]
            reached[y] = 1

for x, y in xy:
    print(c[x-1] + c[y-1])

Submission status: Time Limit Exceeded

Solution code:
import collections
import sys
input = sys.stdin.readline
N = int(input())
abc = [map(int, input().split()) for i in range(N-1)]

Q, K = map(int, input().split())
xy = [map(int, input().split()) for i in range(Q)]
k = [set() for i in range(N)]
g = [[-1]*N for i in range(N)]
for a, b, c in abc:
    g[a-1][b-1] = c
    g[b-1][a-1] = c
    k[a-1].add(b-1)
    k[b-1].add(a-1)
c = [10**9*N]*N
c[K-1] = 0
q = collections.deque([K])
while(len(q) > 0):
    x = q.popleft()

    for y in k[x-1]:
        if c[y] == (10**9*N):
            q.append(y+1)
        c[y] = min(c[x-1]+g[x-1][y], c[y])

for x, y in xy:
    print(c[x-1] + c[y-1])

Submission status: Time Limit Exceeded

Solution code:
import collections
N = int(input())
abc = [map(int, input().split()) for i in range(N-1)]

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

g = [[-1]*N for i in range(N)]
for a, b, c in abc:
    g[a-1][b-1] = c
    g[b-1][a-1] = c

c = [10**9*N]*N
c[K-1] = 0
q = collections.deque([K])
while(len(q) > 0):
    x = q.popleft()

    for j in range(N):
        if g[x-1][j] != -1:
            if c[j] == (10**9*N):
                q.append(j+1)
            c[j] = min(c[x-1]+g[x-1][j], c[j])

for x, y in xy:
    print(c[x-1] + c[y-1])

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import csgraph_from_dense, dijkstra
import sys
input = sys.stdin.readline
N = int(input())
abc = [map(int, input().split()) for i in range(N-1)]

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

g = [[10**9+1]*N for i in range(N)]

for a, b, c in abc:
    g[a-1][b-1] = c
    g[b-1][a-1] = c

G = csgraph_from_dense(g, null_value=10**9+1)

g2 = dijkstra(G)
for x, y in xy:
    print(int(g2[x-1][K-1] + g2[K-1][y-1]))

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import csgraph_from_dense, dijkstra
N = int(input())
abc = [map(int, input().split()) for i in range(N-1)]

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

g = [[10**9+1]*N for i in range(N)]

for a, b, c in abc:
    g[a-1][b-1] = c
    g[b-1][a-1] = c

G = csgraph_from_dense(g, null_value=10**9+1)

g2 = dijkstra(G)
for x, y in xy:
    print(int(g2[x-1][K-1] + g2[K-1][y-1]))

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
N = int(input())
abc = [map(int, input().split()) for i in range(N-1)]

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

g = [[10**9+1]*N for i in range(N)]

for a, b, c in abc:
    g[a-1][b-1] = c
    g[b-1][a-1] = c

G = csgraph_from_dense(g, null_value=10**9+1)

g2 = floyd_warshall(G)
for x, y in xy:
    print(int(g2[x-1][K-1] + g2[K-1][y-1]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra
import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines

N = int(input())
lines = readlines()
edge = np.array([line.split() for line in lines[:N-1]],np.int64).T
graph = csr_matrix((edge[2], (edge[:2] - 1)), (N, N))
Q, K = map(int,lines[N-1].split())
#XY = [list(map(int,line.split())) for line in lines[N:]]
XY = np.array([line.split() for line in lines[N:]],np.int64).T
distance_mat_K = dijkstra(graph, directed = False, indices = K-1)

for i in range(Q):
  print(int(distance_mat_K[XY[0][i]-1]+ distance_mat_K[XY[1][i]-1]))

Submission status: Time Limit Exceeded

Solution code:
def main():
  import numpy as np
  from scipy.sparse import csr_matrix
  from scipy.sparse.csgraph import dijkstra

  N = int(input())
  edge = np.array([input().split() for _ in range(N-1)], dtype = np.int64).T
  graph = csr_matrix((edge[2], (edge[:2] - 1)), (N, N))
  Q, K = map(int,input().split())
  XY = [list(map(int,input().split())) for _ in range(Q)]

  distance_mat_K = dijkstra(graph, directed = False, indices = K-1)

  for i in range(Q):
    print(int(distance_mat_K[XY[i][0]-1]+ distance_mat_K[XY[i][1]-1]))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

N = int(input())
edge = np.array([input().split() for _ in range(N-1)], dtype = np.int64).T
graph = csr_matrix((edge[2], (edge[:2] - 1)), (N, N))
Q, K = map(int,input().split())
XY = [list(map(int,input().split())) for _ in range(Q)]

distance_mat_K = dijkstra(graph, directed = False, indices = K-1)

for i in range(Q):
  print(int(distance_mat_K[XY[i][0]-1]+ distance_mat_K[XY[i][1]-1]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

N = int(input())
edge = np.array([input().split() for _ in range(N-1)], dtype = np.int64).T
graph = csr_matrix((edge[2], (edge[:2] - 1)), (N, N))
Q, K = map(int,input().split())
XY = [list(map(int,input().split())) for _ in range(Q)]

distance_mat_K = dijkstra(graph, directed = False, indices = K-1)
#print(distance_mat_K)

for i in range(Q):
  print(int(dijkstra(graph, directed = False, indices = XY[i][0]-1)[K-1] + distance_mat_K[XY[i][1]-1]))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
graph=[[float("INF")]*(N+1) for _ in range(N+1)]
E ={i:[] for i in range(N+1)}
for i in range(N-1):
  a,b,c = [int(x) for x in input().split()]
  E[a].append([b,c])
  E[b].append([a,c])
Q,K = [int(x) for x in input().split()]
cost= [0]*(N+1)
stk=[[K,-1,0]]
while stk:
  v,p,c = stk.pop()
  if cost[v]!=0:
    continue
  cost[v]=c
  for i,j in E[v]:
    if i!=p:
      stk.append([i,v,c+j])
for i in range(Q):
  a,b = [int(x) for x in input().split()]
  print(cost[a]+cost[b])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
graph=[[float("INF")]*(N+1) for _ in range(N+1)]
for i in range(N-1):
  a,b,c = [int(x) for x in input().split()]
  graph[a][b] =c
  graph[b][a] =c
for k in range(N+1):
  for i in range(N+1):
    for j in range(N+1):
      if i==j:
        graph[i][j]=0
      graph[i][j] = min(graph[i][j],graph[i][k]+graph[k][j])
Q,K = [int(x) for x in input().split()]
for i in range(Q):
  a,b = [int(x) for x in input().split()]
  print(graph[a][K]+graph[K][b])

Submission status: Time Limit Exceeded

Solution code:
#70d
import sys
from functools import lru_cache

sys.setrecursionlimit(1000000000)
INF = (10**5) * (10**9) + 100

N = int(input())

point_list = [[] for _ in range(N+1)]
distance_list = [[] for _ in range(N+1)]

for _ in range(0,N-1):
    a,b,c = map(int, input().split())
    if b not in point_list[a]:
        point_list[a].append(b)
        distance_list[a].append(c)
        point_list[b].append(a)
        distance_list[b].append(c)

@lru_cache(maxsize=1000000000)
def spread_point(from_point,now_point,goal):

    #終了条件　1.ゴールに到達した
    if now_point == goal:
        return 0
    #終了条件　2.行き止まり
    if len(point_list[now_point])==1 and point_list[now_point][0]==from_point:
        return INF
    
    answer_candidate_list = []
    
    #分岐   
    for i in range(len(point_list[now_point])):
        next_point = point_list[now_point][i]
    
        if next_point != from_point:
            #print(now_point,"→",next_point,"   …",distance_list[now_point][i])
            ans_cand = spread_point(now_point,next_point,goal)+distance_list[now_point][i]
            answer_candidate_list.append(ans_cand)
            if ans_cand < (10**5) * (10**9):
              break
            
    return min(answer_candidate_list)


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

for i in range(0,Q):
    x,y = map(int, input().split())
    x_to_K = spread_point(x,x,K)
    y_to_K = spread_point(y,y,K)
    print(x_to_K + y_to_K)

Submission status: Time Limit Exceeded

Solution code:
#70d
import sys
from functools import lru_cache

sys.setrecursionlimit(1000000000)
INF = (10**5) * (10**9) + 100

N = int(input())

point_list = [[] for _ in range(N+1)]
distance_list = [[] for _ in range(N+1)]

for _ in range(0,N-1):
    a,b,c = map(int, input().split())
    if b not in point_list[a]:
        point_list[a].append(b)
        distance_list[a].append(c)
        point_list[b].append(a)
        distance_list[b].append(c)

@lru_cache(maxsize=1000000000)
def spread_point(from_point,now_point,goal):

    #終了条件　1.ゴールに到達した
    if now_point == goal:
        return 0
    #終了条件　2.行き止まり
    if len(point_list[now_point])==1 and point_list[now_point][0]==from_point:
        return INF
    
    answer_candidate_list = []
    
    #分岐   
    for i in range(len(point_list[now_point])):
        next_point = point_list[now_point][i]
    
        if next_point != from_point:
            #print(now_point,"→",next_point,"   …",distance_list[now_point][i])
            answer_candidate_list.append(spread_point(now_point,next_point,goal)+distance_list[now_point][i])
            
    return min(answer_candidate_list)


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

for i in range(0,Q):
    x,y = map(int, input().split())
    x_to_K = spread_point(x,x,K)
    y_to_K = spread_point(y,y,K)
    print(x_to_K + y_to_K)

Submission status: Time Limit Exceeded

Solution code:
# bellman_fordは重いのでTLE

from collections import namedtuple
import sys

input = sys.stdin.readline


def solve():
    inf = 10 ** 14 + 10

    Edge = namedtuple('Edge', 'cost from_ to')

    def bellman_ford(s):
        # 始点sから各頂点への最短距離
        # O(VE) <- dijkstraならO(E log V)だが負辺は無理
        dist = [inf] * n
        dist[s] = 0

        while True:
            update = False
            for e_ in e:
                if dist[e_.from_] != inf and dist[e_.to] > dist[e_.from_] + e_.cost:
                    dist[e_.to] = dist[e_.from_] + e_.cost
                    update = True
            if not update:
                break
        return dist

    n = int(input())
    e = set()
    for _ in range(n - 1):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        e.add(Edge(cost=c, from_=a, to=b))
        e.add(Edge(cost=c, from_=b, to=a))

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

    d = bellman_ford(v)

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


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
from collections import namedtuple
import sys

input = sys.stdin.readline


def solve():
    inf = 10 ** 14 + 10

    Edge = namedtuple('Edge', 'cost from_ to')

    def bellman_ford(s):
        # 始点sから各頂点への最短距離
        dist = [inf] * n
        dist[s] = 0

        while True:
            update = False
            for e_ in e:
                if dist[e_.from_] != inf and dist[e_.to] > dist[e_.from_] + e_.cost:
                    dist[e_.to] = dist[e_.from_] + e_.cost
                    update = True
            if not update:
                break
        return dist

    n = int(input())
    e = set()
    for _ in range(n - 1):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        e.add(Edge(cost=c, from_=a, to=b))
        e.add(Edge(cost=c, from_=b, to=a))

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

    d = bellman_ford(v)

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


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

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

inf = 10 ** 14 + 10

Edge = namedtuple('Edge', ('cost', 'to'))


def dijkstra(s):
    used = [False] * n
    used[s] = True

    dist = [inf] * n
    dist[s] = 0

    h = []
    for e_ in e[s]:
        heappush(h, e_)

    while h:
        c, v = heappop(h)
        if used[v]:
            continue
        used[v] = True
        dist[v] = c
        for e_ in map(lambda x: (x.cost + dist[v], x.to), e[v]):
            heappush(h, e_)
    return dist


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

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

g = dijkstra(v)

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

# warshall_floyd
# n大で無理

# inf = 10 ** 14 + 10
#
# n = int(input())
# g = [[inf] * n for _ in range(n)]
# for i in range(n):
#     g[i][i] = 0
# for _ in range(n - 1):
#     a, b, c = map(int, input().split())
#     a -= 1
#     b -= 1
#     g[a][b] = c
#     g[b][a] = c
#
# for k in range(n):
#     for i in range(n):
#         for j in range(n):
#             g[i][j] = min(g[i][j], g[i][k] + g[k][j])
#
# q, v = map(int, input().split())
# v -= 1
# for _ in range(q):
#     x, y = map(int, input().split())
#     x -= 1
#     y -= 1
#     print(g[x][v] + g[v][y])
#

Submission status: Time Limit Exceeded

Solution code:
import sys
from scipy.sparse.csgraph import dijkstra, csgraph_from_dense
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

N = int(readline())
INF = float('inf')
graph = [[INF] * (N + 1) for _ in range(N + 1)]
for i in range(N + 1):
    graph[i][i] = 0

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

Q, K = map(int, readline().split())
graph = csgraph_from_dense(graph, null_value=INF)
distance = dijkstra(graph, indices=K)

xy = map(int, read().split())
for x, y in zip(xy, xy):
    print(int(distance[x] + distance[y]))

Submission status: Time Limit Exceeded

Solution code:
import sys
from scipy.sparse.csgraph import dijkstra
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

N = int(readline())
INF = float('inf')
graph = [[INF] * (N + 1) for _ in range(N + 1)]
for i in range(N + 1):
    graph[i][i] = 0

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

Q, K = map(int, readline().split())
distance = dijkstra(graph, indices=K)

xy = map(int, read().split())
for x, y in zip(xy, xy):
    print(int(distance[x] + distance[y]))

Submission status: Time Limit Exceeded

Solution code:
import sys, scipy
import numpy as np
from scipy.sparse import csr_matrix, isspmatrix_csr, isspmatrix_csc, isspmatrix
from scipy.sparse.csgraph._shortest_path import shortest_path
n=int(input())

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

G=csr_matrix(g)

q,k=map(int,input().split())
k-=1
d=shortest_path(G, method="D")

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from scipy.sparse.csgraph import floyd_warshall
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

N = int(readline())
INF = float('inf')
graph = [[INF] * (N + 1) for _ in range(N + 1)]
for i in range(N + 1):
    graph[i][i] = 0

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

distance = floyd_warshall(graph, directed=False)

Q, K = map(int, readline().split())
xy = map(int, read().split())
for x, y in zip(xy, xy):
    print(int(distance[x][K] + distance[K][y]))

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
g=[[float("inf")]*n for _ in range(n)]
for _ in range(n-1):
    a,b,c=map(int,input().split())
    a,b=a-1,b-1
    g[a][b]=c
    g[b][a]=c
for i in range(n):
    g[i][i]=0
q,k=map(int,input().split())
k-=1

#V=n E=n-1

d=[float("inf")]*n
d[k]=0
used=[0]*n

while True:
    v=-1
    for u in range(n):
        if (not used[u] and (v==-1 or d[u]<d[v])):
            v=u
    if v==-1:
        break
    used[v]=1
    for u in range(n):
        d[u]=min(d[u],d[v]+g[v][u])

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

Submission status: Time Limit Exceeded

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

n = int(input())
cost = [10**10]*n
edge = [dict() for _ in range(n)]
for _ in range(n-1):
    a, b, c = map(int, input().split())
    edge[a-1].update({b-1: c})
    edge[b-1].update({a-1: c})

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


def dfs(i, prev, d):
    cost[i] = d
    for j in edge[i].keys():
        if j == prev:
            continue
        dfs(j, i, d+edge[i][j])


dfs(K-1, -1, 0)

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

cost = [[float("inf") for i in range(n)] for _ in range(n)]
for i in range(n-1):
    a,b,c = map(int,input().split())
    cost[a-1][b-1] = c
    cost[b-1][a-1] = c
for i in range(n):
    cost[i][i] = 0

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

def dijkstra(s,n,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

d = dijkstra(k-1,n,cost)
ans = []
for i in range(q):
    x,y = map(int,input().split())
    ans.append(d[x-1]+d[y-1])
print(*ans , sep = "\n")

Submission status: Time Limit Exceeded

Solution code:

import sys
def input():
    return sys.stdin.readline()[:-1]

n = int(input())

cost = [[float("inf") for i in range(n)] for _ in range(n)]
for i in range(n-1):
    a,b,c = map(int,input().split())
    cost[a-1][b-1] = c
    cost[b-1][a-1] = c
for i in range(n):
    cost[i][i] = 0

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

def dijkstra(s,n,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

d = dijkstra(k-1,n,cost)
ans = []
for i in range(q):
    x,y = map(int,input().split())
    ans.append(d[x-1]+d[y-1])
print(*ans , sep = "\n")

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
def warshall_floyd(d,k):
    for x in range(n):
        for y in range(n):
            for z in range(n):
                d[y][z] = min(d[y][z],d[y][x]+d[x][z])
    return d[k-1]

graph = [[float("inf") for x in range(n)] for _ 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

for i in range(n):
    graph[i][i] = 0
q,k = map(int,input().split())
G = warshall_floyd(graph,k)
ans = []

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]

n=int(input())
def warshall_floyd(d):
    for x in range(n):
        for y in range(n):
            for z in range(n):
                d[y][z] = min(d[y][z],d[y][x]+d[x][z])
    return d 

graph = [[float("inf")]*n for _ 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

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

G = warshall_floyd(graph)

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

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

Submission status: Time Limit Exceeded

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

n = int(input())
def warshall_floyd(d):
    for x in range(n):
        for y in range(n):
            for z in range(n):
                d[y][z] = min(d[y][z],d[y][x]+d[x][z])
    return d 

graph = [[float("inf")]*n for _ 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

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

G = warshall_floyd(graph)

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

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

def warshall_floyd(d):
    for x in range(n):
        for y in range(n):
            for z in range(n):
                d[y][z] = min(d[y][z],d[y][x]+d[x][z])
    return d
    

graph = [[float("inf")]*n for _ 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

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

G = warshall_floyd(graph)

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

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

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
g=[[] for i in range(n)]
for i in range(n-1):
    a,b,c=map(int,input().split())
    g[a-1].append([b-1,c])
    g[b-1].append([a-1,c])
q,k=map(int,input().split())
qu=[[k-1,0]]
v=[0]*n
d=[0]*n
while len(qu)>0:
    s=qu[0]
    qu=qu[1:]
    v[s[0]]=1
    for j in g[s[0]]:
        if not v[j[0]]:
            v[j[0]]=1
            d[j[0]]=s[1]+j[1]
            qu+=[[j[0],d[j[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())
g=[[] for i in range(n)]
for i in range(n-1):
    a,b,c=map(int,input().split())
    g[a-1].append([b-1,c])
    g[b-1].append([a-1,c])
q,k=map(int,input().split())
qu=[[k-1,0]]
v=[0]*n
d=[0]*n
while len(qu)>0:
    s=qu.pop(0)
    v[s[0]]=1
    for j in g[s[0]]:
        if not v[j[0]]:
            v[j[0]]=1
            d[j[0]]=s[1]+j[1]
            qu.append([j[0],d[j[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:
import sys
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
n = int(input())
graph = [[0 for i in range(n)] for j in range(n)]
for j in range(n-1):
    a, b, c = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    graph[a][b] = c
    graph[b][a] = c
q, k = [int(i) for i in sys.stdin.readline().split()]
k -= 1
res = dijkstra(csr_matrix(graph), indices=k)
for i in range(q):
    x, y = [int(i) for i in sys.stdin.readline().split()]
    x -= 1
    y -= 1
    print(int(res[x] + res[y]))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def main():
    n=int(input())
    dis=[[10**20 for i in range(n)] for i in range(n)]
    g=[[] for i in range(n)]
    for _ in range(n-1):
        a,b,c = map(int,input().split())
        g[a-1].append(b-1)
        g[b-1].append(a-1)
        dis[a-1][b-1] = c
        dis[b-1][a-1] = c
    q,k = map(int,input().split())
    k-=1
    d=deque([k])
    f=[False for i in range(n)]
    dis[k][k]=0
    while d:
        s= d.popleft()
        f[s]= True
        for sg in g[s]:
            if not f[sg]:
                dis[k][sg]= dis[k][s]+dis[s][sg]
                d.append(sg)
    lq=[]
    for _ in range(q):
        lq.append(list(map(int,input().split())))
    for sq in lq:
        print(dis[k][sq[0]-1]+dis[k][sq[1]-1])

main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
from heapq import heappush,heappop
qqq=[[10**15 for _ in range(n)]for _ in range(n)]
for i in range(n-1):
	x,y,z=map(int,input().split())
	qqq[x-1][y-1]=z
	qqq[y-1][x-1]=z
dis=[10**15 for _ in range(n)]
qq,k=map(int,input().split())
dis[k-1]=0
s=set()
for i in range(n):
	q=10**15
	for j in range(n):
		if (j not in s) and q>dis[j]:
			q=dis[j]
			lit=j
	s.add(lit)
	for j in range(n):
		if j not in s:
			if dis[j]>dis[lit]+qqq[lit][j]:
				dis[j]=dis[lit]+qqq[lit][j]
for i in range(qq):
	r,t=map(int,input().split())
	print(dis[r-1]+dis[t-1])