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:
N = int(input())
from heapq import heapify, heappush, heappop

inf = float("inf")
def dijkstra(graph, start):  # graphは隣接リスト(繋がっている先, コスト)
    vsize = len(graph)
    dist = [inf] * vsize
    seen = [False] * vsize
    prev = [None] * vsize
    pq = []
    heapify(pq)

    dist[start] = 0
    heappush(pq, (0, start))  # heapではtuple[0]で比較されるのでこの順番で追加する
    while pq:
        cost, u = heappop(pq)
        seen[u] = True
        if dist[u] < cost:
            continue
        for v, w in graph[u]:
            temp_cost = dist[u] + w
            if not seen[v] and temp_cost < dist[v]:
                dist[v] = temp_cost
                prev[v] = u
                heappush(pq, (dist[v], v))
    return dist
graph = [[] 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))
shortest_path = [dijkstra(graph, i) for i in range(N)]
Q, K = map(int, input().split())
for _ in range(Q):
    x, y = map(int, input().split())
    print(shortest_path[x-1][K-1]+shortest_path[K-1][y-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.buffer.readline
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    N = int(readline())
    A = []
    B = []
    C = []
    for _ in range(N-1):
        a,b,c = map(int, readline().split())
        a -= 1
        b -= 1
        A += [a,b]
        B += [b,a]
        C += c,c

    Q,K = map(int, readline().split())
    L = dijkstra(csr_matrix((C, (A, B)), shape=(N, N)),indices=K-1)
    for _ in range(Q):
        x,y = map(int, readline().split())
        print(int(L[x-1]+L[y-1]))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
edges = []
for i in range(N-1):
    a, b, c = map(int, input().split())
    edges.append([a-1, b-1, c])
    edges.append([b-1, a-1, c])
Q, K = map(int, input().split())
K -= 1
def bellman_ford(edges, num_v, start):
    dist = [float('inf') for _ in range(num_v)]
    dist[start] = 0

    changed = True
    while changed:
        changed = False
        for edge in edges:
            if dist[edge[1]] > dist[edge[0]] + edge[2]:
                dist[edge[1]] = dist[edge[0]] + edge[2]
                changed = True
    return dist

ans_list = []
base = bellman_ford(edges, N, K)
for i in range(Q):
    x, y = map(lambda n: int(n) - 1, input().split())
    x_K = base[x]
    K_y = base[y]
    ans_list.append(x_K + K_y)

for i in ans_list:
    print(i)

Submission status: Time Limit Exceeded

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


ans_list = []
def dijkstra(edges, num_v, start):
    dist = [float('inf')] * num_v
    dist[start] = 0
    q = []
    heapq.heappush(q, [0, start])

    while len(q) > 0:
        _, u = heapq.heappop(q)
        for edge in edges[u]:
            if dist[edge[0]] > dist[u] + edge[1]:
                dist[edge[0]] = dist[u] + edge[1]
                heapq.heappush(q, [dist[u] + edge[1], edge[0]])
    return dist
for i in range(Q):
    x, y = map(lambda n: int(n) - 1, input().split())
    x_K = dijkstra(edges, N, x)[K]
    K_y = dijkstra(edges, N, K)[y]
    ans_list.append(x_K + K_y)

for i in ans_list:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
edges = []
for i in range(N-1):
    a, b, c = map(int, input().split())
    edges.append([a-1, b-1, c])
    edges.append([b-1, a-1, c])
Q, K = map(int, input().split())
K -= 1
def bellman_ford(edges, num_v, start):
    dist = [float('inf') for _ in range(num_v)]
    dist[start] = 0

    changed = True
    while changed:
        changed = False
        for edge in edges:
            if dist[edge[1]] > dist[edge[0]] + edge[2]:
                dist[edge[1]] = dist[edge[0]] + edge[2]
                changed = True
    return dist

ans_list = []

for i in range(Q):
    x, y = map(lambda n: int(n) - 1, input().split())
    x_K = bellman_ford(edges, N, x)[K]
    K_y = bellman_ford(edges, N, K)[y]
    ans_list.append(x_K + K_y)

for i in ans_list:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
 
n = int(input())
V = defaultdict(list)

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

def dfs(source):
    dist = [-1]*(n+1)
    dist[source] = 0
    q = [source]
    while q:
        a = q.pop()
        for b in V[a]:
            if dist[b[0]]!=-1:
                continue
            dist[b[0]] = dist[a] + b[1]
            q.append(b[0])
    return dist

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

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

Submission status: Time Limit Exceeded

Solution code:

from collections import deque
N=int(input())
T=[[] for _ in range(N)]
for i in range(N-1):
    a,b,c=map(int, input().split())
    T[a-1].append((b-1,c))
    T[b-1].append((a-1,c))

Q,K=map(int, input().split())
que=[(K-1,0)]
done=[-1]*N
while que:
    t=que.pop(0)
    now,nowd=t
    done[now]=nowd
    for nex in T[now]:
        nexnode,nexd=nex
        if done[nexnode]!=-1:
            continue
        else:
            que.append((nexnode, nowd+nexd))

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

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
cost=[[float("inf")]*N for _ in range(N)]
graph=[[] for _ in range(N)]
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)
    cost[a][b]=c
    cost[b][a]=c

def dijkstra(start,cost):
    d=[float("inf")]*N
    used=[False]*N
    d[start]=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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N=int(input())
cost=[[float("inf")]*N for _ in range(N)]
graph=[[] for _ in range(N)]
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)
    cost[a][b]=c
    cost[b][a]=c

def dfs(start):
    visited=[False]*N
    queue=deque([start])
    visited[start]=0
    while queue:
        x=queue.pop()
        for y in graph[x]:
            if visited[y]!=False:
                continue
            visited[y]=visited[x]+cost[x][y]
            queue.append(y)
    return visited

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
def ep(*s):
    print(*s,file=sys.stderr)

def search(x,y):
    c = 0
    ox = nodes[x]
    oy = nodes[y]
    while ox.level != oy.level:
        if ox.level > oy.level:
            c += cost[(ox.parent,ox.n)]
            ox = nodes[ox.parent]
        if ox.level < oy.level:
            c += cost[(oy.parent,oy.n)]
            oy = nodes[oy.parent]
    while ox.n != oy.n:
        c += cost[(ox.parent,ox.n)]
        ox = nodes[ox.parent]
        c += cost[(oy.parent,oy.n)]
        oy = nodes[oy.parent]
    return c

class node:
    def __init__(self,n):
        self.n = n
        self.parent = -1
        self.children = set()
        self.level = -1
    def __repr__(self):
        #return f"node={self.n},parent={self.parent},level={self.level},ch={self.children}"
        return "n={0},p={1},l={2},ch{3}".format(self.n,self.parent,self.level,self.children)
    
    
n = int(input())
cost = {}
path = defaultdict(lambda: set())
for i in range(n-1):
    (ai,bi,ci) = list(map(int,input().split()))
    (ai,bi) = sorted([ai,bi])
    cost[(ai,bi)] = ci
    cost[(bi,ai)] = ci
    path[ai].add(bi)
    path[bi].add(ai)

(q,k) = list(map(int,input().split()))
dp = defaultdict(int)

# 各ノードの階層を調べる
nodes = {}
lv = 0
lst = [(k,-1)]
lst2 = []
term = 0

while len(lst) > 0:
    ep(lst)
    for (i,p) in lst:
        o = node(i)
        o.parent = p
        o.children = path[i].copy()
        if o.parent in o.children:
            o.children.remove(o.parent)
        o.level = lv
        nodes[i] = o
        lst2 += list(map(lambda x:(x,i),list(o.children)))
    lst = lst2
    lst2 = []
    lv += 1
ep(nodes)
for i in range(q):
    (x,y) = list(map(int,input().split()))
    print(search(x,k) + search(k,y))

Submission status: Time Limit Exceeded

Solution code:
import queue

n = int(input())
my_dict = dict()
mtx = dict()

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

    if b in my_dict:
        my_dict[b].append(a)
    else:
        my_dict[b] = [a]

    ma = max(a, b)
    mi = min(a, b)
    mtx[ma * (10 ** 10) + mi] = c

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

ret_dict = dict()

q = queue.Queue()
q.put((k-1, 0))
ret_dict[k-1] = 0

while not q.empty():
    ptr, length = q.get()
    if ptr in my_dict:
        for item in my_dict[ptr]:
            if item not in ret_dict:
                ma = max(ptr, item)
                mi = min(ptr, item)
                q.put((item, length + mtx[ma * (10 ** 10) + mi]))
                ret_dict[item] = length + mtx[ma * (10 ** 10) + mi]

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

Submission status: Time Limit Exceeded

Solution code:
import queue

n = int(input())
my_dict = dict()
mtx = dict()

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

    if b in my_dict:
        my_dict[b].append(a)
    else:
        my_dict[b] = [a]

    ma = max(a, b)
    mi = min(a, b)
    mtx[(ma, mi)] = c

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

ret_dict = dict()

q = queue.Queue()
q.put((k-1, 0))
ret_dict[k-1] = 0

while not q.empty():
    ptr, length = q.get()
    if ptr in my_dict:
        for item in my_dict[ptr]:
            if item not in ret_dict:
                ma = max(ptr, item)
                mi = min(ptr, item)
                q.put((item, length + mtx[(ma, mi)]))
                ret_dict[item] = length + mtx[(ma, mi)]

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

Submission status: Time Limit Exceeded

Solution code:
import queue

n = int(input())
my_dict = dict()
mtx = dict()

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

    if b in my_dict:
        my_dict[b].append(a)
    else:
        my_dict[b] = [a]
    mtx[(a, b)] = c
    mtx[(b, a)] = c

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

ret_dict = dict()

q = queue.Queue()
q.put((k-1, 0))
ret_dict[k-1] = 0

while not q.empty():
    ptr, length = q.get()
    if ptr in my_dict:
        for item in my_dict[ptr]:
            if item not in ret_dict:
                q.put((item, length + mtx[(ptr, item)]))
                ret_dict[item] = length + mtx[(ptr, item)]

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

Submission status: Time Limit Exceeded

Solution code:
import queue

n = int(input())
my_dict = dict()
mtx = dict()

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

    if b in my_dict:
        my_dict[b].append(a)
    else:
        my_dict[b] = [a]
    mtx[(a, b)] = c
    mtx[(b, a)] = c

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

ret_dict = dict()
visited = set()

q = queue.Queue()
q.put((k-1, 0))
visited.add(k-1)

while not q.empty():
    ptr, length = q.get()
    if ptr in my_dict:
        for item in my_dict[ptr]:
            if item not in visited:
                q.put((item, length + mtx[(ptr, item)]))
                ret_dict[item] = length + mtx[(ptr, item)]
                visited.add(item)

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

Submission status: Time Limit Exceeded

Solution code:
import queue

n = int(input())
my_dict = dict()
mtx = [[0] * n for _ in range(n)]

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

    if b in my_dict:
        my_dict[b].append(a)
    else:
        my_dict[b] = [a]
    mtx[a][b] = c
    mtx[b][a] = c

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

ret_dict = dict()
visited = set()

q = queue.Queue()
q.put((k-1, 0))
visited.add(k-1)

while not q.empty():
    ptr, length = q.get()
    if ptr in my_dict:
        for item in my_dict[ptr]:
            if item not in visited:
                q.put((item, length + mtx[ptr][item]))
                ret_dict[item] = length + mtx[ptr][item]
                visited.add(item)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N = int(input())

g = [[] for _ in range(N+1)]
dist = [[-1]*(N+1) for _ in range(N+1)]
for i 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())

cost = [-1] * (N+1)
cost[K] = 0
temp = [K]
while temp:
    p = temp.pop()
    for q in g[p]:
        if cost[q[0]] == -1:
            cost[q[0]] = cost[p] + q[1]
            temp.append(q[0])

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

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import csgraph_from_dense,dijkstra

N = int(input())
edge = [[-1]*(N+2)for i in range(N+2)]

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

G = csgraph_from_dense(edge, null_value=-1)
d = dijkstra(G,indices = K)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N = int(input())

g = [[] for _ in range(N+1)]
dist = [[-1]*(N+1) for _ in range(N+1)]
for i in range(N-1):
    a, b, c = map(int, input().split())
    g[a].append(b)
    g[b].append(a)
    dist[a][b] = c
    dist[b][a] = c
    
Q, K = map(int, input().split())

cost = [-1] * (N+1)
cost[K] = 0
temp = [[K, 0]]
while temp:
    p = temp.pop()
    gset = set(g[p[0]])
    gset.discard(p[1])
    for q in gset:
        cost[q] = cost[p[0]] + dist[p[0]][q]
        temp.append([q, p[0]])

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

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import csgraph_from_dense,dijkstra

N = int(input())
edge = [ [10**9+1 for j in range(N+1)] for i in range(N+1) ]

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

G = csgraph_from_dense(edge, null_value=10**9+1)
d = dijkstra(G,indices = K)

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

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import csgraph_from_dense,dijkstra

N = int(input())
edge = [ [10**10 for j in range(N+1)] for i in range(N+1) ]

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

G = csgraph_from_dense(edge, null_value=10**10)
d = dijkstra(G,indices = K)

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

g = [[] for _ in range(N+1)]
dist = [[-1]*(N+1) for _ in range(N+1)]
for i in range(N-1):
    a, b, c = map(int, input().split())
    g[a].append(b)
    g[b].append(a)
    dist[a][b] = c
    dist[b][a] = c
    
Q, K = map(int, input().split())

cost = [-1] * (N+1)
cost[K] = 0
temp = [[K, 0]]
while temp:
    p = temp.pop()
    gset = set(g[p[0]])
    gset.discard(p[1])
    for q in gset:
        cost[q] = cost[p[0]] + dist[p[0]][q]
        temp.append([q, p[0]])

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

g = [[] for _ in range(N+1)]
dist = [[-1]*(N+1) for _ in range(N+1)]
for i in range(N-1):
    a, b, c = map(int, input().split())
    g[a].append(b)
    g[b].append(a)
    dist[a][b] = c
    dist[b][a] = c
    
Q, K = map(int, input().split())

cost = [-1] * (N+1)
cost[K] = 0
temp = [K]
while temp:
    p = temp.pop()
    for q in g[p]:
        if cost[q] != -1: continue
        cost[q] = cost[p] + dist[p][q]
        temp.append(q)

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

Submission status: Time Limit Exceeded

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

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

g = [[] for _ in range(N+1)]
dist = [[-1]*(N+1) for _ in range(N+1)]
for a, b, c in abc:
    g[a].append(b)
    g[b].append(a)
    dist[a][b] = c
    dist[b][a] = c

cost = [-1] * (N+1)
cost[K] = 0
temp = [K]
while temp:
    p = temp.pop()
    for q in g[p]:
        if cost[q] != -1: continue
        cost[q] = cost[p] + dist[p][q]
        temp.append(q)

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

g = [[] for _ in range(N+1)]
dist = [[-1]*(N+1) for _ in range(N+1)]
for a, b, c in abc:
    g[a].append(b)
    g[b].append(a)
    dist[a][b] = c
    dist[b][a] = c

f_inf = float('inf')
cost = [f_inf] * (N+1)
cost[K] = 0
temp = deque([K])

while temp:
    p = temp.popleft()
    for q in g[p]:
        c = cost[p] + dist[p][q]
        if cost[q] >= c:
            cost[q] = c
            temp.append(q)
            
for x, y in xy:
    print(cost[x] + cost[y])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
from collections import deque
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n=int(input())
tree=[[] for i in range(n+1)]
for i in range(n-1):
    a,b,c=mp()
    tree[a].append((b,c))
    tree[b].append((a,c))
q,k=mp()
dist=[-1]*(n+1)
dist[k]=0
deq=deque()
deq.append(k)

while len(list(deq))>0:
    p=deq.popleft()
    for x,y in tree[p]:
        if dist[x]==-1:
            dist[x]=dist[p]+y
            deq.append(x)
for i in range(q):
    xi,yi=mp()
    print(dist[xi]+dist[yi])

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop

def dijkstra_heap(s):
    """頂点sから各頂点への最短距離"""
    d = [float("inf") for _ in range(N)]
    used = [True for _ in range(N)]  # True: 未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heappush(edgelist, e)
    while len(edgelist):
        min_edge = heappop(edgelist)
        # まだ使われていない頂点の中から最小距離のものを探す
        if not used[min_edge[1]]:
            continue
        v = min_edge[1]
        d[v] = min_edge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heappush(edgelist, [e[0]+d[v], e[1]])
    return d

N = int(input())

edge = [[] for _ in range(N)]  # edge[i]: i から出る道の[重み、行き先]の配列

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

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

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

Submission status: Time Limit Exceeded

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

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

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

################################
N = int(input())

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

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

zk = dijkstra(K-1, N, N-1, cost)
#print(zk)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(200000)

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

costDic = [0]*(N+1)
def f(cost,now,p):
    costDic[now] = cost
    for nx,c in edges[now].items():
        if nx != p:
            f(cost+c,nx,now)

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

Submission status: Time Limit Exceeded

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]

from collections import defaultdict, deque, Counter
from sys import exit
import heapq
import math
import copy
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)

N = getN()
dist = [[] for i in range(N + 1)]
for i in range(N - 1):
    a, b, c = getNM()
    dist[a].append([b, c])
    dist[b].append([a, c])
d = [[float('inf')] * (N + 1) for i in range(N + 1)]
ignore = [-1] * (N + 1)

# Kからの最短距離をbfsで測る
def distance(sta):
    # 木をKから順にたどる（戻るの禁止）
    pos = deque([sta])

    while len(pos) > 0:
        u = pos.popleft()
        for i in dist[u]:
            if ignore[i[0]] == -1:
                ignore[i[0]] = ignore[u] + i[1]
                pos.append(i[0])

Q, K = getNM()
ignore[K] = 0
distance(K)
# 答えはK~xまでの距離+K~yまでの距離
ans = []
for i in range(Q):
    x, y = getNM()
    ans.append(ignore[x] + ignore[y])
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse import csr_matrix, csgraph
N = int(input())
row, column, data = zip(*tuple(tuple(map(lambda n: int(n) - 1, input().split())) for _ in range(N - 1)))
Q, K = map(int, input().split())
dist = csgraph.dijkstra(csr_matrix(([d + 1 for d in data], (row, column)), (N, N), dtype=np.int64), directed=False, indices=[K - 1])[0]
for _ in range(Q):
    indices = list(map(lambda n: int(n) - 1, input().split()))
    print(int(dist[indices].sum()))

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import shortest_path
import sys
import numpy as np
def input():
    return sys.stdin.readline().strip()
 
N = int(input())
 
graph = [[0 for i in range(N)] for j in range(N)]
 
for i in range(N-1):
    a,b,c = map(int,input().split())
    graph[a-1][b-1] = c
    graph[b-1][a-1] = c

Q,K = map(int,input().split())
dist = shortest_path(np.array(graph),indices=K-1)

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

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

distance = [float('inf') for _ in range(n)]
distance[k - 1] = 0

d = deque()
d.append(k - 1)
visited = set({})
while d:
    point = d.popleft()
    for index, value in enumerate(graph[point]):
        if value > 0:
            distance[index] = min(distance[point] + graph[point][index], distance[index])
            if index not in visited:
                d.append(index)
    visited.add(point)
    
for _ in range(q):
    x, y = map(int, input().split())
    print(distance[x - 1] + distance[y - 1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

distance = [float('inf') for _ in range(n)]
distance[k - 1] = 0

d = deque()
d.append(k - 1)

visited = set({})
total = set([i for i in range(n)])
while len(total - visited) > 0:
    point = d.popleft()
    for index, value in enumerate(graph[point]):
        if value > 0:
            distance[index] = min(distance[point] + graph[point][index], distance[index])
            if index not in visited:
                d.append(index)
    visited.add(point)
    
for _ in range(q):
    x, y = map(int, input().split())
    print(distance[x - 1] + distance[y - 1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

distance = [float('inf') for _ in range(n)]
distance[k - 1] = 0

d = deque()
d.append(k - 1)

visited = set({})
total = set([i for i in range(n)])
while len(total - visited) > 0:
    point = d.popleft()
    prev = float('inf')
    for index, value in enumerate(graph[point]):
        if value > 0:
            distance[index] = min(distance[point] + graph[point][index], distance[index])
        if (value <= prev) & (value > 0):
            if index not in visited:
                d.append(index)
    visited.add(point)
    
for _ in range(q):
    x, y = map(int, input().split())
    print(distance[x - 1] + distance[y - 1])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)


n=int(input())

c={}
tree=[[] for _ in range(n)]

for _ in range(n-1):
    i,j,k=map(int,input().split())
    i-=1
    j-=1
    tree[i].append(j)
    tree[j].append(i)
    c[(i,j)]=k
    c[(j,i)]=k

result=[]
q,k=map(int,input().split())

memo=[-1]*n

def DEF(z,cnt):
    global memo,tree,c
    memo[z]=cnt
    for item in tree[z]:
        if memo[item]==-1:
            DEF(item,cnt+c[(item,z)])

DEF(k-1,0)
result=[]
for item in range(q):
    a,b=map(int,input().split())
    result.append(memo[a-1]+memo[b-1])

for item in result:
    print(item)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)


n=int(input())

c={}
tree=[[] for _ in range(n)]

for _ in range(n-1):
    i,j,k=map(int,input().split())
    i-=1
    j-=1
    tree[i].append(j)
    tree[j].append(i)
    c[(i,j)]=k
    c[(j,i)]=k

result=[]
q,k=map(int,input().split())

#初期値が0の辞書
from collections import defaultdict
memo = defaultdict(lambda: -1) 

def DEF(z,cnt):
    global memo,tree,c
    memo[z]=cnt
    for item in tree[z]:
        if memo[item]==-1:
            DEF(item,cnt+c[(item,z)])

DEF(k-1,0)
result=[]
for item in range(q):
    a,b=map(int,input().split())
    result.append(memo[a-1]+memo[b-1])

for item in result:
    print(item)

Submission status: Time Limit Exceeded

Solution code:
def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d


n = int(input())
w = n - 1
cost = [[float("inf") for i in range(n)] for i in range(n)] 
for i in range(w):
    x,y,z = map(int,input().split())
    cost[x-1][y-1] = z
    cost[y-1][x-1] = z

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

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