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())
l = [list(map(int,input().split())) for _ in range(n-1)]

dp = [[0 for _ in range(n)] for _ in range(n)]
INF = 10**18
for i in range(n):
    for j in range(n):
        if i!=j:
            dp[i][j] = INF
for a,b,c in l:
    dp[a-1][b-1] = c
    dp[b-1][a-1] = c
#print(dp)

#最短リスト
for c in range(n):
    for f in range(n):
        for la in range(n):
            dp[f][la] = min(dp[f][la] , dp[f][c] +  dp[c][la])

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

Submission status: Time Limit Exceeded

Solution code:
import networkx as nx

N = int(input())

T = nx.Graph()

for _ in range(N-1):
    a, b, c = map(int, input().split())
    T.add_edge(a, b, weight=c)

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

for _ in range(Q):
    x, y = map(int, input().split())
    d_p = nx.dijkstra_path_length(T, x, K)
    d_q = nx.dijkstra_path_length(T, K, y)
    d = d_p + d_q
    print(d)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import defaultdict
    from heapq import heappop, heappush
    N = int(input())
    edge = defaultdict(list)
    length = []
    
    
    for i in range(N):
        length.append([0]*N)
    for i in range(N-1):
        a,b,c = map(int,input().split())
        a -= 1
        b -= 1
        edge[a].append(b)
        edge[b].append(a)
        length[a][b] = length[b][a] = c
    Q,K = map(int,input().split())
    K -= 1
    cost = [0]*N
    length[K][K] = 0
    targets = [(0,K)]
    cost = [10**18]*N
    cost[K] = 0
    visited = [False]*N
    while targets:
        c,t = heappop(targets)
        if visited[t]:
            continue
        cost[t] = c
        visited[t] = True
        for v in edge[t]:
            if cost[v] > cost[t] + length[t][v]:
                heappush(targets,(cost[t] + length[t][v],v))

    out = []
    for i in range(Q):
        x,y = map(lambda x: int(x)-1, input().split())
        out.append(cost[x]+cost[y])

    print('\n'.join(map(str,out)))







main()

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 i in range(N)] for i 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

Q, K = map(int, input().split())
    
ans = dijkstra(K-1, N, N-1, cost)
for i in range(Q):
    x, y = map(int, input().split())
    print(ans[x-1] + ans[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 i in range(N)] for j 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

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

Submission status: Time Limit Exceeded

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

def abc070_d():
    read = sys.stdin.buffer.read
    inp = iter(map(int, read().split()))

    n = next(inp)
    adjmtx = lil_matrix((n, n), dtype=int)
    for _ in range(n-1):
        a = next(inp) - 1
        b = next(inp) - 1
        c = next(inp)
        adjmtx[a, b] = c
        adjmtx[b, a] = c

    q = next(inp)
    k = next(inp) - 1

    dist = dijkstra(csgraph=adjmtx, indices=k)
    eps = 1e-6

    for _ in range(q):
        x = next(inp) - 1
        y = next(inp) - 1
        ans = int(dist[x] + dist[y] + eps)
        print(ans)

if __name__ == '__main__':
    abc070_d()

Submission status: Time Limit Exceeded

Solution code:
def abc070_d():
    import sys
    read = sys.stdin.buffer.read
    inp = iter(map(int, read().split()))

    import numpy as np
    from scipy.sparse import lil_matrix
    from scipy.sparse.csgraph import dijkstra

    n = next(inp)
    adjmtx = lil_matrix((n, n), dtype=np.int32)
    for _ in range(n-1):
        a = next(inp) - 1
        b = next(inp) - 1
        c = next(inp)
        adjmtx[a, b] = c
        adjmtx[b, a] = c

    q = next(inp)
    k = next(inp) - 1

    dist = dijkstra(csgraph=adjmtx, indices=k)
    eps = 1e-6

    for _ in range(q):
        x = next(inp) - 1
        y = next(inp) - 1
        ans = int(dist[x] + dist[y] + eps)
        print(ans)

if __name__ == '__main__':
    abc070_d()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
readline = sys.stdin.readline
n = int(readline())
D = [[-1]*n for _ in range(n)]
for i in  range(n): D[i][i]=0
G = [[] for _ in range(n)]
for i in range(n-1):
    a,b,c = map(lambda x:int(x)-1, map(int, readline().split()))
    G[a].append(b)
    G[b].append(a)
    D[a][b] = c+1
    D[b][a] = c+1

q, k = map(int, readline().split())
k -= 1
que = deque([k])
_D = [-1]*n
_D[k] = 0
while que:
    nw = que.popleft()
    d = _D[nw]
    for nx in G[nw]:
        if nw!=k and _D[nx]!=-1: continue
        _D[nx] = d+D[nw][nx]
        que.append(nx)

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
from decimal import Decimal # 10進数で考慮できる

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N = int(input())

graph = [[mod for i in range(N)] for i in range(N)]

weights = {}

roots = [[] for i in range(N)]
for i in range(N - 1):
    a, b, c = LI()
    a -= 1
    b -= 1
    roots[a].append(b)
    roots[b].append(a)
    weights[(a,b)] = c
    weights[(b,a)] = c

Q, K = LI()
K -= 1
xy = [0 for i in range(Q)]
for i in range(Q):
    x, y = LI()
    x -= 1
    y -= 1
    xy[i] = [x, y]
"""
xyzで全部の通りを見つけるとN ** 3で無理
なので今回は木構造に注目してBFS or DFSで解いたらいいのでは？
"""

visited = [-1 for i in range(N)]
queue = collections.deque()
queue.append(K)
visited[K] = 0

while len(queue)> 0:
    node = queue.popleft()
    cnt = visited[node]
    for n_node in roots[node]:
        if visited[n_node] == -1:
            visited[n_node] = cnt + weights[(node, n_node)]
            queue.append(n_node)
for x, y in xy:
    print(visited[x] + visited[y])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
from decimal import Decimal # 10進数で考慮できる

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N = int(input())

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

roots = [[] for i in range(N)]
for i in range(N - 1):
    a, b, c = LI()
    a -= 1
    b -= 1
    graph[a][b] = c
    graph[b][a] = c
    roots[a].append(b)
    roots[b].append(a)

Q, K = LI()
K -= 1
xy = [0 for i in range(Q)]
for i in range(Q):
    x, y = LI()
    x -= 1
    y -= 1
    xy[i] = [x, y]
"""
xyzで全部の通りを見つけるとN ** 3で無理
なので今回は木構造に注目してBFS or DFSで解いたらいいのでは？
"""

visited = [-1 for i in range(N)]
queue = collections.deque()
queue.append(K)
visited[K] = 0

while len(queue)> 0:
    node = queue.popleft()
    cnt = visited[node]
    for n_node in roots[node]:
        if visited[n_node] == -1:
            visited[n_node] = cnt + graph[node][n_node]
            queue.append(n_node)
for x, y in xy:
    print(visited[x] + visited[y])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n=int(input())
e=[[] for _ in range(n+1)]
l=[[0]*(n+1) for _ in range(n+1)]
dist=[-1]*(n+1)
for i in range(n-1):
    a,b,c=map(int,input().split())
    e[a].append(b)
    e[b].append(a)
    l[a][b]=c
    l[b][a]=c
q,k=map(int,input().split())
a=deque()
a.append((k,0))
while a:
    x,d=a.popleft()
    dist[x]=d
    for j in e[x]:
        if dist[j]!=-1:
            continue
        else:
            a.append((j,d+l[x][j]))
ans=[]
for i in range(q):
    x,y=map(int,input().split())
    ans.append(dist[x]+dist[y])
print(*ans,sep="\n")

Submission status: Time Limit Exceeded

Solution code:
import queue

N = int(input())
d = [[1 << 64] * N for _ in range(N)]
for i in range(N):
    d[i][i] = 0
for _ in range(N - 1):
    a, b, c = map(int, input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c
Q, K = map(int, input().split())
K -= 1
x, y = [0] * Q, [0] * Q
for i in range(Q):
    x[i], y[i] = map(int, input().split())

que = queue.PriorityQueue()
k = [1 << 64] * N
k[K] = 0
que.put((0, K))

while not que.empty():
    cost, vertex = que.get()
    if k[vertex] < cost:
        continue
    for i in range(N):
        if k[i] > k[vertex] + d[vertex][i]:
            k[i] = k[vertex] + d[vertex][i]
            que.put((k[i], i))

for i in range(Q):
    print(k[x[i]-1] + k[y[i]-1])

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
import sys
input = sys.stdin.readline

n = int(input())
A = []
B = []
C = []

for i in range(n-1):
    a, b, c = list(map(int, input().split()))
    A.append(a-1)
    B.append(b-1)
    C.append(c)

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

d = dijkstra(csr_matrix((C, (A, B)), shape = (n, n)), directed=False, indices=k).astype(int)

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

Submission status: Time Limit Exceeded

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

def dijkstra(s, N, G, x, y):
    d = [20 ** 9] * N
    d[s] = 0
    hq = [[0, s]]
    heapq.heapify(hq)
    while len(hq) > 0:
        v, i = heapq.heappop(hq)
        if d[i] < v:
            continue
        for c, j in G[i]:
            if d[j] > d[i] + c:
                d[j] = d[i] + c
                heapq.heappush(hq, [d[j], j])
    return d[x] + d[y]

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

for d in dist:
    print(d)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
G = [[20 ** 9 for _ in range(N + 1)] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b, c = map(int, input().split())
    G[a - 1][b - 1] = c
    G[b - 1][a - 1] = c
Q, K = map(int, input().split())

def dijkstra(s, N, G, x, y):
    d = [20 ** 9] * 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 i in range(N):
            d[i] = min(d[i], d[v] + G[v][i])
    
    return d[x] + d[y]

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

for d in dist:
    print(d)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
G = [[20 ** 9 for _ in range(N + 1)] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b, c = map(int, input().split())
    G[a - 1][b - 1] = c
    G[b - 1][a - 1] = c
Q, K = map(int, input().split())

def dijkstra(s, N, G, g):
    d = [20 ** 9] * 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 i in range(N):
            d[i] = min(d[i], d[v] + G[v][i])
    
    return d[g]

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

for d in dist:
    print(d)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
G=[[] for _ 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())

SD=[0]*N

for x,d in G[K-1]:
    SD[x]=d

for i in range(N):
    if i==K-1:continue
    ans=[]
    seen=[0]*N
    stack=[[i,0]]
    seen[i]=1
    while stack:
        x,d=stack.pop()
        if x==K-1:
            ans.append(d)
        elif SD[x]!=0:
            ans.append(d+SD[x])
        else:
            for y,co in G[x]:
                if seen[y]==0:
                    stack.append([y,d+co])
                    seen[y]=1
    SD[i]=min(ans)


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

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
G=[[] for _ 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())

SD=[0]*N

for i in range(N):
    if i==K-1:continue
    ans=[]
    seen=[0]*N
    stack=[[i,0]]
    seen[i]=1
    while stack:
        x,d=stack.pop()
        if x==K-1:
            ans.append(d)
        elif SD[x]!=0:
            ans.append(d+SD[x])
        else:
            for y,co in G[x]:
                if seen[y]==0:
                    stack.append([y,d+co])
                    seen[y]=1
    SD[i]=min(ans)


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

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
G=[[] for _ 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())

SD=[0]*N

for i in range(N):
    if i==K-1:continue
    ans=[]
    seen=[0]*N
    stack=[[i,0]]
    seen[i]=1
    while stack:
        x,d=stack.pop()
        if x==K-1:
            ans.append(d)
        else:
            for y,co in G[x]:
                if seen[y]==0:
                    stack.append([y,d+co])
                    seen[y]=1
    SD[i]=min(ans)


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

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import csgraph_from_dense, dijkstra
inf = 10 ** 10

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

G = csgraph_from_dense(edge, null_value = inf)
q, k = map(int,input().split())
d = dijkstra(G, False, indices= k - 1)
for _ in range(q):
    x, y = map(int,input().split())
    dis = d[x - 1] + d[y - 1]
    print(int(dis))

Submission status: Time Limit Exceeded

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

TO_K = []
TREE = []
DISTANCE = []

def dfs(child, parent):
    for i_node in TREE[parent]:
        if i_node[0] == child:
            TO_K[child] = TO_K[parent] + i_node[1]

    for i_gch in TREE[child]:
        if i_gch[0] == parent:
            TO_K[child] = TO_K[parent] + i_gch[1]
        else:
            dfs(i_gch[0], child)

    return


def main():
    n = int(input())
    abc = [[int(_) for _ in input().split()] for i in range(n-1)]
    q, k = map(int, input().split())
    xy = [[int(_) for _ in input().split()] for i in range(q)]

    global TO_K
    # index '0' is not used.
    TO_K = [0]*(n+1)

    global TREE
    # index '0' is not used.
    TREE = [[] for _ in range(n+1)]
    for a, b, c in abc:
        TREE[a].append([b, c])
        TREE[b].append([a, c])

    dfs(k, 0)

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


if __name__ == "__main__":
    main()
    sys.exit(0)

Submission status: Time Limit Exceeded

Solution code:
import sys

TO_K = []
TREE = []
DISTANCE = []

def dfs(child, parent):
    TO_K[child] = TO_K[parent] + DISTANCE[parent][child]

    for i_gch in TREE[child]:
        if i_gch == parent:
            continue
        dfs(i_gch, child)

    return


def main():
    n = int(input())
    abc = [[int(_) for _ in input().split()] for i in range(n-1)]
    q, k = map(int, input().split())
    xy = [[int(_) for _ in input().split()] for i in range(q)]

    global TO_K
    # index '0' is not used.
    TO_K = [0]*(n+1)

    global TREE
    global DISTANCE
    # index '0' is not used.
    TREE = [[] for _ in range(n+1)]
    DISTANCE = [[0]*(n+1) for _ in range(n+1)]
    for a, b, c in abc:
        TREE[a].append(b)
        TREE[b].append(a)
        DISTANCE[a][b] = c
        DISTANCE[b][a] = c

    dfs(k, 0)

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


if __name__ == "__main__":
    main()
    sys.exit(0)

Submission status: Time Limit Exceeded

Solution code:
import sys

 
from collections import defaultdict
import heapq
import sys


        
def dijkstra(startvertex,V,graph):
    distances=[sys.maxsize]*V
    distances[startvertex]=0
    heap=[(0,startvertex)]
    while heap:
        current_distance,current_vertex=heapq.heappop(heap)
        if current_distance>distances[current_vertex]:
            continue
        for neighbor in range(len(graph[current_vertex])):
            if graph[current_vertex][neighbor]>0:
                distance=current_distance+graph[current_vertex][neighbor]
                
                
                if distance<distances[neighbor]:
                    distances[neighbor]=distance
                    heapq.heappush(heap,(distance,neighbor))
                    
    return distances
n=int(input())   
sys.setrecursionlimit(10**9)
    
graph=[[0 for i in range(n)]for j in range(n)]
for i in range(n-1):
    a=[int(x) for x in input().split()]
    # print(a)
    graph[a[0]-1][a[1]-1]=a[2]
    graph[a[1]-1][a[0]-1]=a[2]

# print(graph)
w=[int(x) for x in input().split()]
m=dijkstra(w[1]-1,n,graph)
# print(m)
c=0
for i in range(w[0]):
    s=[int(x) for x in input().split()]
    # print(s)
    c=abs(m[s[0]-1])+abs(m[s[1]-1])
    print(c)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
 
from collections import defaultdict
import heapq
import sys


        
def dijkstra(startvertex,V,graph):
    distances=[sys.maxsize]*V
    distances[startvertex]=0
    heap=[(0,startvertex)]
    while heap:
        current_distance,current_vertex=heapq.heappop(heap)
        if current_distance>distances[current_vertex]:
            continue
        for neighbor in range(len(graph[current_vertex])):
            if graph[current_vertex][neighbor]>0:
                distance=current_distance+graph[current_vertex][neighbor]
                
                
                if distance<distances[neighbor]:
                    distances[neighbor]=distance
                    heapq.heappush(heap,(distance,neighbor))
                    
    return distances
n=int(input())            
    
graph=[[0 for i in range(n)]for j in range(n)]
for i in range(n-1):
    a=[int(x) for x in input().split()]
    # print(a)
    graph[a[0]-1][a[1]-1]=a[2]
    graph[a[1]-1][a[0]-1]=a[2]

# print(graph)
w=[int(x) for x in input().split()]
m=dijkstra(w[1]-1,n,graph)
# print(m)
c=0
for i in range(w[0]):
    s=[int(x) for x in input().split()]
    # print(s)
    c=abs(m[s[0]-1])+abs(m[s[1]-1])
    print(c)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import heapq
import sys


        
def dijkstra(startvertex,V,graph):
    distances=[sys.maxsize]*V
    distances[startvertex]=0
    heap=[(0,startvertex)]
    while heap:
        current_distance,current_vertex=heapq.heappop(heap)
        if current_distance>distances[current_vertex]:
            continue
        for neighbor in range(len(graph[current_vertex])):
            if graph[current_vertex][neighbor]>0:
                distance=current_distance+graph[current_vertex][neighbor]
                
                
                if distance<distances[neighbor]:
                    distances[neighbor]=distance
                    heapq.heappush(heap,(distance,neighbor))
                    
    return distances
n=int(input())            
    
graph=[[0 for i in range(n)]for j in range(n)]
for i in range(n-1):
    a=[int(x) for x in input().split()]
    # print(a)
    graph[a[0]-1][a[1]-1]=a[2]
    graph[a[1]-1][a[0]-1]=a[2]

# print(graph)
w=[int(x) for x in input().split()]
m=dijkstra(w[1]-1,n,graph)
# print(m)
c=0
for i in range(w[0]):
    s=[int(x) for x in input().split()]
    # print(s)
    c=abs(m[s[0]-1])+abs(m[s[1]-1])
    print(c)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import heapq
import sys


        
def dijkstra(startvertex,V,graph):
    distances=[sys.maxsize]*V
    distances[startvertex]=0
    heap=[(0,startvertex)]
    while heap:
        current_distance,current_vertex=heapq.heappop(heap)
        if current_distance>distances[current_vertex]:
            continue
        for neighbor in range(len(graph[current_vertex])):
            if graph[current_vertex][neighbor]>0:
                distance=current_distance+graph[current_vertex][neighbor]
                
                
                if distance<distances[neighbor]:
                    distances[neighbor]=distance
                    heapq.heappush(heap,(distance,neighbor))
                    
    return distances
n=int(input())            
    
graph=[[0 for i in range(n)]for j in range(n)]
for i in range(n-1):
    a=map(int,raw_input().split())
    # print(a)
    graph[a[0]-1][a[1]-1]=a[2]
    graph[a[1]-1][a[0]-1]=a[2]

# print(graph)
w=map(int,raw_input().split())
m=dijkstra(w[1]-1,n,graph)
# print(m)
c=0
for i in range(w[0]):
    s=map(int,raw_input().split())
    # print(s)
    c=abs(m[s[0]-1])+abs(m[s[1]-1])
    print(c)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
query = [[0]*N for _ in range(N)]
for _ in range(N-1):
    a, b, c = mapint()
    query[a-1][b-1] = c
    query[b-1][a-1] = c

Q, K = mapint()
from collections import deque
stack = deque([(K-1, 0, -1)])
dist = [0]*N
while stack:
    now, cnt, per = stack.pop()
    lis = query[now]
    dist[now] = cnt
    for nx, c in enumerate(lis):
        if nx==per:
            continue
        if c!=0:
            stack.append((nx, cnt+c, now))

for _ in range(Q):
    x, y = mapint()
    print(dist[x-1]+dist[y-1])

Submission status: Time Limit Exceeded

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

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

limit = 100010
depth = [0] * limit

def dfs(v, p, d): # (現在の頂点v, vの親, 現在の距離)
    depth[v] = d
    for e in tree[v]:
        if e[0] == p: continue
        dfs(e[0], v, d + e[1])

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

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra
from sys import stdin
nii=lambda:map(int,stdin.readline().split())

n=int(input())

row,col,w=[],[],[]
for i in range(n-1):
  a,b,c=nii()
  row.append(a-1)
  col.append(b-1)
  w.append(c)

q,k=nii()
k-=1

g=csr_matrix((w,(row,col)),shape=(n,n))
d=dijkstra(g,indices=k,directed=False)

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def main():
    n = int(input())
    G = [[] for _ in range(n)]
    D = [[] for _ in range(n)]
    for _ in range(n - 1):
        a, b, c = list(map(int, input().split()))
        a -= 1
        b -= 1
        G[a].append(b)
        D[a].append(c)
        G[b].append(a)
        D[b].append(c)
    q, k = list(map(int, input().split()))
    k -= 1
    stack = deque([k, ])
    ans = [-1] * n
    ans[k] = 0
    while stack:
        x = stack.popleft()
        for dx, l in zip(G[x], D[x]):
            if ans[dx] == -1:
                ans[dx] = ans[x] + l
                stack.appendleft(dx)
    for _ in range(q):
        x, y = list(map(lambda x: int(x) - 1, input().split()))
        print(ans[x] + ans[y])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
graph = [[0] * (N+1) for i in range(N+1)]
for i in range(N-1):
    a, b, c = map(int, input().split())
    graph[a][b] = c
    graph[b][a] = c
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, \
    bellman_ford, johnson
from scipy.sparse import csr_matrix

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

a = np.array(graph)
path = dijkstra(a, indices=K)
# print(path)

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

Submission status: Time Limit Exceeded

Solution code:
import heapq

n = int(input())

g = [[] for _ 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))

ans = []
q, k = map(int, input().split())
for i in range(q):
    x, y = map(int, input().split())
    
    res = 0
    # x -> k
    dis = [float("inf")] * n
    dis[x-1] = 0
    pq = [(0, x-1)]
    while pq:
        d, node = heapq.heappop(pq)
        if d > dis[node]: continue

        for nxt, cost in g[node]:
            if d + cost < dis[nxt]:
                dis[nxt] = d + cost
                heapq.heappush(pq, (dis[nxt], nxt))
    res += dis[k-1]
    # k -> y
    dis = [float("inf")] * n
    dis[k-1] = 0
    pq = [(0, k-1)]
    while pq:
        d, node = heapq.heappop(pq)
        if d > dis[node]: continue

        for nxt, cost in g[node]:
            if d + cost < dis[nxt]:
                dis[nxt] = d + cost
                heapq.heappush(pq, (dis[nxt], nxt))
    res += dis[y-1]
    ans.append(res)

print("\n".join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
import heapq

INF = 10**15
n = int(input())
dist_mat = [[INF]*n for _ in range(n)]
edges = [[] for _ in range(n)]
for i in range(n-1):
    a, b, c = map(int,input().split())
    a -= 1
    b -= 1
    dist_mat[a][b] = c
    dist_mat[b][a] = c
    edges[a].append(b)
    edges[b].append(a)
    dist_mat[i][i] = 0

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

que = [(0, k)]
heapq.heapify(que)
costs = [INF]*n
costs[k] = 0
while len(que) > 0:
    dist, current = heapq.heappop(que)
    for edge in edges[current]:
        if costs[edge] > costs[current] + dist_mat[current][edge]:
            costs[edge] = costs[current] + dist_mat[current][edge]
            heapq.heappush(que, (costs[edge], edge))

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

for ans in res:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq

INF = 10**30
n = int(input())
dist_mat = [[INF]*n for _ in range(n)]
edges = [[] for _ in range(n)]
for i in range(n-1):
    a, b, c = map(int,input().split())
    a -= 1
    b -= 1
    dist_mat[a][b] = c
    dist_mat[b][a] = c
    edges[a].append(b)
    edges[b].append(a)
    dist_mat[i][i] = 0

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

que = [(0, k)]
heapq.heapify(que)
costs = [INF]*n
costs[k] = 0
while len(que) > 0:
    dist, current = heapq.heappop(que)
    for edge in edges[current]:
        if costs[edge] > costs[current] + dist_mat[current][edge]:
            costs[edge] = costs[current] + dist_mat[current][edge]
            heapq.heappush(que, (costs[edge], edge))

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

for ans in res:
    print(ans)

Submission status: Time Limit Exceeded

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


N = int(input())

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

# make tree
G2 = [-1] * (N + 1)


def f(v, c, p):
    if G2[v] != -1: return
    G2[v] = c

    for nv, nc in G[v]:
        if nv == p: continue
        f(nv, nc + c, v)


f(K, 0, 0)

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