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

class Graph():
    def __init__(self,n,edge):
        self.n = n
        self.graph = [[0]*n for _ in range(n)]
        self.edge = edge
        self.ed_list = [[] for _ in range(n)]
        for a,b,c in edge:
            self.ed_list[a].append([b,c])
            self.ed_list[b].append([a,c])
    
    def dijkstra(self,start):
        INF = float('inf')
        cost = [INF]*self.n
        cost[start] = 0
        from heapq import heappop,heappush
        stack = [[0, start]]
        while stack:
            c, x = heappop(stack)
            for to,j in self.ed_list[x]:
                if cost[to] > j + c:
                    cost[to] = j + c
                    heappush(stack,[j + c, to])
        return cost

gp = Graph(n,edge)
cost = gp.dijkstra(k-1)
for i,j in querry:
    print(cost[i] + cost[j])

Submission status: Time Limit Exceeded

Solution code:
#D問題
N=int(input())
AB=[]
C=[]
for i in range(N-1):
    a,b,c=map(int,input().split())
    AB.append([a-1,b-1])
    C.append(c)

Q,K=map(int,input().split())
XY=[list(map(int,input().split())) for i in range(Q)]
depth=[0 for i in range(N)]
def DFS(v,p,d):
    depth[v]=d
    ever=[0 for i in range(N)]
    ever[v]=1
    for i in range(N):
        if ([i,v] in AB or [v,i] in AB) and ever[i] == 0:
            if [i,v] in AB:
                depth_index=AB.index([i,v])
            else:
                depth_index=AB.index([v,i])
            if i == p:
                pass
            else:
                DFS(i,v,d+C[depth_index])
        else:
            pass
    return
DFS(K-1,-1,0)
for i in range(Q):
    X=XY[i][0]-1
    Y=XY[i][1]-1
    print(depth[X]+depth[Y])

Submission status: Time Limit Exceeded

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

INF = np.inf

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

Q, K = map(int, input().split())
ans_graph = dijkstra(csgraph,directed=False,indices=K)


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

Submission status: Time Limit Exceeded

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

INF = np.inf

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

Q, K = map(int, input().split())
ans_graph = dijkstra(csgraph,indices=K)


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

Submission status: Time Limit Exceeded

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

INF = np.inf

N = int(input())
csgraph = [[np.inf for i in range(N+1)] for i in range(N+1)]
for i in range(N-1):
  a, b, c = map(int, input().split())
  csgraph[a][b] = c
  csgraph[b][a] = c

Q, K = map(int, input().split())
ans_graph = dijkstra(csgraph,indices=K)


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

Submission status: Time Limit Exceeded

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

INF = np.inf

N = int(input())
csgraph = [[np.inf for i in range(N+1)] for i in range(N+1)]
for i in range(N-1):
  a, b, c = map(int, input().split())
  csgraph[a][b] = c
  csgraph[b][a] = c

csgraph = dijkstra(csgraph)

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

Submission status: Time Limit Exceeded

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

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

#defaultdict(<class 'list'>, {1: [[2, 1], [3, 1]], 2: [[1, 1], [3, 3]], 3: [[1, 1], [2, 3]]})
 
def DIJKSTRA(point,d):
    cost      = {node:float("inf") for node in d.keys()}
    preference= {node:None         for node in d.keys()}#最適路のこと 
    Q         = set(d.keys())  #頂点のリスト
    cost[point]=0  #開始地点のコストをゼロとする（当たり前
    while True:
        prefnd=min(Q, key=lambda c:cost[c]) #最適な点探し
        Q.remove(prefnd)  #最適だった点を削除
        if len(Q)==0:
            break #全部の点消したら終了
        for p,c in d[prefnd]:  #次の点とそこまでのコスト
            temp=cost[prefnd]+c  #スタートからそこまでのコストを計算
            if temp<cost[p]:   #計算してみたコストがそこに行くまでの最小値ならば
                cost[p]=temp #最小値更新
                preference[p]=prefnd
    return preference,cost  #点のつながりとコスト例 1から１に０ １から２に１ １から３に２

q,k=map(int,input().split())
x,y=DIJKSTRA(k,d)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
inf=100000000000000000000
fastinput=sys.stdin.readline
N=int(fastinput())
path=[[0]*N for hoge in range(N)]
for fuga in range(N-1):
    a,b,c=[int(hoge) for hoge in fastinput().split()]
    path[a-1][b-1]=c
    path[b-1][a-1]=c
Q,K=[int(hoge) for hoge in fastinput().split()]
stack=deque()
stack.append(K-1)
Kcost=[0]*N#あとあと初期化
went=[False]*N
went[K-1]=True
while stack:
    cur=stack.pop()
    curcost=Kcost[cur]
    for next,c in enumerate(path[cur]):
        if c and not went[next]:
            went[next]=True
            Kcost[next]=curcost+c
            stack.append(next)
for q in range(Q):
    x,y=[int(hoge) for hoge in fastinput().split()]
    print(Kcost[x-1]+Kcost[y-1])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
d = [0] * N
INF = float('inf')

cost = [[INF] * N for i 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
    
def dijkstra(s):
    used = [False] * N
    for i in range(N):
        d[i] = INF
    d[s] = 0
    
    while True:
        v = -1
        for u in range(N):
            if used[u] == False and (v == -1 or d[u] < d[v]):
                v = u
        if v == -1:
            break
        used[v] = True
        
        for u in range(N):
            d[u] = min(d[u], d[v] + cost[v][u])
            
Q, K = map(int, input().split())

dijkstra(K - 1)

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

Submission status: Time Limit Exceeded

Solution code:
import heapq

N = int(input())
d = [0] * N
INF = float('inf')

class Info:
    def __init__(self, to, cost):
        self.to = to
        self.cost = cost
        
G = [[] for i in range(N)]
for _ in range(N - 1):
    a, b, c = map(int, input().split())
    G[a - 1].append(Info(b - 1, c))
    G[b - 1].append(Info(a - 1, c))
    
def dijkstra(s):
    for i in range(N):
        d[i] = INF
    d[s] = 0
    h = []
    heapq.heappush(h, [0, s])
    
    while h != []:
        p = heapq.heappop(h)
        v = p[1]
        if d[v] < p[0]:
            continue
        for i in range(len(G[v])):
            e = G[v][i]
            if d[e.to] > d[v] + e.cost:
                d[e.to] = d[v] + e.cost
                heapq.heappush(h, [d[e.to], e.to])

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
d = [0] * N
INF = float('inf')

cost = [[INF] * N for i 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
    
def dijkstra(s):
    used = [False] * N
    for i in range(N):
        d[i] = INF
    d[s] = 0
    
    while True:
        v = -1
        for u in range(N):
            if used[u] == False and (v == -1 or d[u] < d[v]):
                v = u
        if v == -1:
            break
        used[v] = True
        
        for u in range(N):
            d[u] = min(d[u], d[v] + cost[v][u])
            
Q, K = map(int, input().split())
for _ in range(Q):
    ans = 0
    x, y = map(int, input().split())
    dijkstra(x - 1)
    ans += d[K - 1]
    #print(d)
    dijkstra(K - 1)
    ans += d[y - 1]
    #print(d)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import floyd_warshall as wf

N = int(input())
INF = float('inf')

d = [[INF] * (N) for i 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
    
wf = wf(d)

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def connected(ros, f):
    ls = []
    for r in ros:
        if r[0] == f:
            ls.append((r[1], r))
        elif r[1] == f:
            ls.append((r[0], r))
    return ls

def solve1(ros, k):
    costs = {k: 0}
    #routes = {}
    queue = deque([k])
    added = set()
    while True:
        if not queue:
            break
        p = queue.popleft()
        for ne in connected(ros, p):
            if ne[0] not in added:
                queue.append(ne[0])
                added.add(ne[0])
                #routes[ne[0]] = p
                costs[ne[0]] = costs[p] + ne[1][2]
    return costs

n = int(input())
rs = []
for i in range(n - 1):
    abc = input().split(' ')
    rs.append([int(x) for x in abc])
qk = input().split(' ')
q = int(qk[0])
k = int(qk[1])
qs = []
for i in range(q):
    xy = input().split(' ')
    qs.append([int(x) for x in xy])

c = solve1(rs, k)

for query in qs:
    c1 = c[query[0]]
    c2 = c[query[1]]
    print(c1 + c2)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def connected(ros, f):
    ls = []
    for r in ros:
        if r[0] == f:
            ls.append((r[1], r))
        elif r[1] == f:
            ls.append((r[0], r))
    return ls

def solve(ros, f, t):
    costs = {}
    routes = {}
    queue = deque([f])
    added = set()
    while True:
        p = queue.popleft()
        if p == t:
            break
        for ne in connected(ros, p):
            if ne[0] not in added:
                queue.append(ne[0])
                added.add(ne[0])
                costs[ne[0]] = ne[1][2]
                routes[ne[0]] = p
    ans = 0
    pointer = t
    while True:
        ans += costs[pointer]
        pointer = routes[pointer]
        if pointer == f:
            return ans
    

n = int(input())
rs = []
for i in range(n - 1):
    abc = input().split(' ')
    rs.append([int(x) for x in abc])
qk = input().split(' ')
q = int(qk[0])
k = int(qk[1])
qs = []
for i in range(q):
    xy = input().split(' ')
    qs.append([int(x) for x in xy])

for query in qs:
    c1 = solve(rs, query[0], k)
    c2 = solve(rs, k, query[1])
    print(c1 + c2)

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict

def dfs(start, dest, pre, d):
    if d[start][dest] > 0:
        return d[start][dest]

    for i in range(len(d)):
        if d[start][i] > 0 and i != pre:
            c = dfs(i, dest, start, d)
            if c > 0:
                return d[start][i] + dfs(i, dest, start, d)

    return 0

def main():
    input = sys.stdin.readline
    N = int(input())
    
    tree = defaultdict(lambda: [])
    d = [[0 for _ in range(N)] for _ in range(N)]
    for _ in range(N-1):
        a, b, c = map(int, input().split())
        a, b = a - 1, b - 1
        
        d[a][b] = c
        d[b][a] = c

    Q, K = map(int, input().split())
    k_dist = [0 for _ in range(N)]
    for i in range(N):
        k_dist[i] = dfs(K-1, i, -1, d)

    for _ in range(Q):
        x, y = map(int, input().split())
        x, y = x - 1, y - 1

        print(int(k_dist[x] + k_dist[y]))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def main():
    input = sys.stdin.readline
    N = int(input())
    
    inf = float('inf')
    d = [[inf for _ in range(N)] for _ in range(N)]
    for _ in range(N-1):
        a, b, c = map(int, input().split())
        d[a-1][b-1] = c
        d[b-1][a-1] = c

    D = floyd_warshall(np.array(d))

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def distances(tree: list, treeSize: int, root: int)->list:
    dists = [0] * treeSize

    q = [(root, -1, 0)]

    while len(q) > 0:
        v, prev, d2v = q[0]
        q = q[1:]

        dists[v] = d2v
        for u, dv2u in tree[v]:
            if prev == u:
                continue
            q.append((u, v, d2v + dv2u))

    return dists


def transit_tree_path(
        N: int, edges: list, Q: int, K: int, queries: list)->list:
    tree = [[] for _ in range(N)]
    for u, v, c in edges:
        tree[u-1].append((v-1, c))
        tree[v-1].append((u-1, c))

    d = distances(tree, N, K-1)

    return [d[x-1]+d[y-1] for x, y in queries]


if __name__ == "__main__":
    N = int(input())
    edges = [tuple(map(int, input().split())) for _ in range(N-1)]
    Q = 0
    Q, K = map(int, input().split())
    queries = [tuple(map(int, input().split())) for _ in range(Q)]

    ans = transit_tree_path(N, edges, Q, K, queries)
    for a in ans:
        print(a)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
from collections import defaultdict
from collections import deque
branch=defaultdict(set)
for i in range(N-1):
    a,b,c=map(int,input().split())
    branch[a]|={(b,c),}
    branch[b]|={(a,c),}
Q,K=map(int,input().split())
dist=[float('inf')]*(N+1)
dist[K]=0
check=deque([(K,set())])

while len(check)>0:
    now=check.popleft()
    for nex,c in branch[now[0]]:
        if nex not in now[1]:
            dist[nex]=min(dist[nex],dist[now[0]]+c)
            check.append((nex,now[1]|{now[0]}))
for q in range(Q):
    x,y=map(int,input().split())
    print(dist[x]+dist[y])

Submission status: Time Limit Exceeded

Solution code:
import heapq
class edge:
    def __init__(self,to,cost):
        self.to=to
        self.cost=cost

N=int(input())
G=[list() for i in range(N)]
for i in range(N-1):
    a,b,c=map(int,input().split())
    G[a-1].append(edge(b-1,c))
    G[b-1].append(edge(a-1,c)) #無向グラフならこれも

def dijkstra(o):
    d=[float('inf') for i in range(N)]
    d[o]=0
    hq=[]
    prev=[[] for i in range(N)]
    heapq.heappush(hq,(0,o))
    while hq:
        p=heapq.heappop(hq)
        v=p[1]
        if(d[v]<p[0]):
            continue
        for i in G[v]:
            if(d[i.to]>d[v]+i.cost):
                d[i.to]=d[v]+i.cost
                prev[i.to]=prev[v]+[str(sorted([v,i.to]))]
                heapq.heappush(hq,(d[i.to],i.to))
    return d,prev

Q,K=map(int,input().split())
d=dijkstra(K-1)[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
input = sys.stdin.readline
N = int(input())
abc = [[int(j) for j in input().split()] for _ in range(N-1)]
Q,K = map(int, input().split())
xy = [ [int(j) for j in input().split()] for _ in range(Q)]

inf = float("inf")
con = [ [] for _ in range(N+1)]
cost = [ [inf] * (N+1) for _ in range(N+1)]

for i in range(N-1):
    a,b,c = abc[i]
    con[a].append(b)
    con[b].append(a)
    cost[a][b] = c
    cost[b][a] = c

q = [(K,0)]
visited = [False] * (N+1)
visited[K] = True
costmap = [inf] * (N+1)
costmap[K] = 0
while q:
    n,cst = q.pop()
    for ch in con[n]:
        if visited[ch]:
            continue
        q.append( (ch, cst+cost[n][ch]))
        visited[ch] = True
        costmap[ch]  = cst+ cost[n][ch]
    
# def dfs(a,b, par):
#     if cost[a][b] != inf :
#         return cost[a][b]
# 
#     if len(list(filter(lambda x: x!=par, con[a]))) == 0:
#         return inf
# 
#     cst = inf
#     idx= -1
#     for e,ch in enumerate(con[a]):
#         if ch == par:
#             continue
#         if cst > cost[a][ch] + dfs(ch,b,a):
#             cst = cost[a][ch] + dfs(ch,b,a)
#             
#             idx = e
#     if idx != -1:
#         cost[a][b] = cst
#         cost[b][a] = cst
#     return cst
# 
for i in range(Q):
    x,y = xy[i]
    print( costmap[x] + costmap[y])
# for i in range(Q):
#     x,y = xy[i]
#     # _ = dfs(K,x,None)
#     # _ = dfs(y,K, None)
#     print(dfs(x,K,None) + dfs(K,y,None))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
abc = [[int(j) for j in input().split()] for _ in range(N-1)]
Q,K = map(int, input().split())
xy = [ [int(j) for j in input().split()] for _ in range(Q)]

inf = float("inf")
con = [ [] for _ in range(N+1)]
cost = [ [inf] * (N+1) for _ in range(N+1)]

for i in range(N-1):
    a,b,c = abc[i]
    con[a].append(b)
    con[b].append(a)
    cost[a][b] = c
    cost[b][a] = c

def dfs(a,b, par):
    if cost[a][b] != inf :
        return cost[a][b]

    if len(list(filter(lambda x: x!=par, con[a]))) == 0:
        return inf

    cst = inf
    idx= -1
    for e,ch in enumerate(con[a]):
        if ch == par:
            continue
        if cst > cost[a][ch] + dfs(ch,b,a):
            cst = cost[a][ch] + dfs(ch,b,a)
            
            idx = e
    if idx != -1:
        cost[a][b] = cst
    return cst

for i in range(Q):
    x,y = xy[i]
    _ = dfs(K,x,None)
    _ = dfs(y,K, None)
    print(dfs(x,K,None) + dfs(K,y,None))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
abc = [[int(j) for j in input().split()] for _ in range(N-1)]
Q,K = map(int, input().split())
xy = [ [int(j) for j in input().split()] for _ in range(Q)]

inf = float("inf")
con = [ [] for _ in range(N+1)]
cost = [ [inf] * (N+1) for _ in range(N+1)]

for i in range(N-1):
    a,b,c = abc[i]
    con[a].append(b)
    con[b].append(a)
    cost[a][b] = c
    cost[b][a] = c

def dfs(a,b, par):
    if cost[a][b] != inf :
        return cost[a][b]
    # if cost[b][a] != inf:
    #     return cost[b][a]

    if len(list(filter(lambda x: x!=par, con[a]))) == 0:
        cost[a][b] = inf
        cost[b][a] = inf
        return inf

    cst = inf
    idx= -1
    for e,ch in enumerate(con[a]):
        if ch == par:
            continue
        if cst > cost[a][ch] + dfs(ch,b,a):
            cst = cost[a][ch] + dfs(ch,b,a)
            idx = e
    if idx != -1:
        mn = min(cst, cost[a][b] , cost[b][a])
        cost[a][b] = mn
        # cost[b][a] = mn
    return cst

for i in range(Q):
    x,y = xy[i]
    print(dfs(x,K,None) + dfs(K,y,None))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
abc = [[int(j) for j in input().split()] for _ in range(N-1)]
Q,K = map(int, input().split())
xy = [ [int(j) for j in input().split()] for _ in range(Q)]

inf = float("inf")
con = [ [] for _ in range(N+1)]
cost = [ [inf] * (N+1) for _ in range(N+1)]

for i in range(N-1):
    a,b,c = abc[i]
    con[a].append(b)
    con[b].append(a)
    cost[a][b] = c
    cost[b][a] = c

def dfs(a,b, par):
    if cost[a][b] != inf:
        return cost[a][b]
    if len(list(filter(lambda x: x!=par, con[a]))) == 0:
        return inf

    cst = inf
    idx= -1
    for e,ch in enumerate(con[a]):
        if ch == par:
            continue
        if cst > cost[a][ch] + dfs(ch,b,a):
            cst = cost[a][ch] + dfs(ch,b,a)
            idx = e
        # cst = min(cst, cost[a][ch] + dfs(ch, b, a))
    if idx != -1:
        cost[a][b] = cst
    return cst

for i in range(Q):
    x,y = xy[i]
    print(dfs(x,K,None) + dfs(K,y,None))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
E = []
for i in range(N - 1):
        E.append([int(n) for n in input().split()])

Q, K = [int(n) for n in input().split()]
P = []
for i in range(Q):
        P.append([int(n) for n in input().split()])

def get_path(start, goal, prev):
    path = []
    now = goal
    path.append(now)
    while True:
        path.append(prev[now])
        if prev[now] == start: break
        now = prev[now]
    path.reverse()
    return path

def search(glaph, start, goal):
    MAX_VAL = 1e18
    g_size = N + 1
    visited = [False] * g_size
    cost = [MAX_VAL] * g_size
    prev = [None] * g_size
    cost[start] = 0
    prev[start] = start
    now = start
    while True:
        min = MAX_VAL
        next = -1
        visited[now] = True
        for i in range(g_size):
            if visited[i]: continue
            flag = False
            cc = None
            for [a, b, c] in E:
                    if (a == now and b == i) or (a == i and b == now):
                            flag = True
                            cc = c
                            break
            if flag:
                tmp_cost = cc + cost[now]
                if cost[i] > tmp_cost:
                    cost[i] = tmp_cost
                    prev[i] = now
            if min > cost[i]:
                min = cost[i]
                next = i
        if next == -1: break
        now = next
    return cost[goal]

for i in range(Q):
        [x, y] = P[i]
        xcost = search(E, x, K)
        ycost = search(E, K, y)
        cost = xcost + ycost
        print(cost)

Submission status: Time Limit Exceeded

Solution code:
#070-D
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return input()

#ベルマンフォード法
#E,vはedge、vertexの数
v=I()
E=v-1
e=[]
for i in range(E): #eの各要素は[始点,終点,コスト]
    f,t,c=map(int,input().split())
    e.append([f-1,t-1,c])
    e.append([t-1,f-1,c])

def sp(s,e): #sは始点、dに各頂点への最短距離が格納される
    d=[None for i in range(v)]
    for i in range(v):
        d[i]=float('INF')
    d[s]=0
    
    while True:
    
        update=False
        for i in range(2*E):
            
            if d[e[i][0]]!=float('INF') and d[e[i][1]]>d[e[i][0]]+e[i][2]:
                d[e[i][1]]=d[e[i][0]]+e[i][2]
                update=True
                
        
        if update==False:
            break
         
    return d
            
q,k=IL()
d=sp(k-1,e)
for i in range(q):
    x,y=IL()
    print(d[x-1]+d[y-1])

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop


class Dijkstra:
    def __init__(self, route_map, start_point, goal_point=None):
        self.route_map = route_map
        self.start_point = start_point
        self.goal_point = goal_point

    def execute(self):
        num_of_vertex = len(self.route_map)
        dist = [float('inf') for _ in range(num_of_vertex)]
        prev = [float('inf') for _ in range(num_of_vertex)]
        dist[self.start_point] = 0
        heap_q = []
        heappush(heap_q, (0, self.start_point))
        while len(heap_q) != 0:
            prev_cost, src = heappop(heap_q)
            if dist[src] < prev_cost:
                continue
            for dest in range(num_of_vertex):
                cost = route_map[src][dest]
                if cost != float('inf') and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
                    heappush(heap_q, (dist[dest], dest))
                    prev[dest] = src
        if self.goal_point is not None:
            return self.get_path(prev)
        else:
            return dist

        def get_path(prev):
            path = [self.goal_point]
            dest = self.goal_point
            while prev[dest] != float('inf'):
                dest = prev[dest]
            return list(reversed(path))


N = int(input())
route_map = [[float('inf') for _ in range(N)] for _ in range(N)]
for _ in range(N - 1):
    a, b, c = map(int, input().split())
    route_map[a - 1][b - 1] = c
    route_map[b - 1][a - 1] = c
Q, K = map(int, input().split())
K -= 1
dijakstra_result = Dijkstra(route_map, K).execute()
for _ in range(Q):
    x, y = map(int, input().split())
    print(dijakstra_result[x - 1] + dijakstra_result[y - 1])

Submission status: Time Limit Exceeded

Solution code:
import queue

N = int(input())
tree = [[] for _ in range(N)]

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

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

depth = [0 for _ in range(N)]

def bfs(v, p = -1, d = 0):
    q = queue.Queue()
    q.put([v, p, d])
    while not q.empty():
        cur = q.get()
        depth[cur[0]] = cur[2]
        for i, j in tree[cur[0]]:
            if i == cur[1]:
                continue
            q.put([i, cur[0], cur[2] + j])

bfs(K)

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
M = N-1
inf = float("inf")
dp = [[inf]*N for _ in [0]*N]
for i in range(N):dp[i][i] = 0
q = [list(map(int, input().split())) for i in range(M)]
Q , K = map(int, input().split())
p = [list(map(int, input().split())) for i in range(Q)]
ans = 0
 
for a,b,c in q:
    dp[a-1][b-1] = c
    dp[b-1][a-1] = c
for k in range(N):
    for i in range(N):
        for j in range(N):
            dp[i][j] = min(dp[i][j],dp[i][k]+dp[k][j])
for a,b in p:
    print(dp[a-1][K-1]+dp[K-1][b-1])

Submission status: Time Limit Exceeded

Solution code:
# N 個の頂点、N-1 個の辺なので K を根にした木構造に変換する

N = int(input())
T = {}
D = [None] * N
F = [True] * N

for n in range(N):
    T[n] = []

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

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

K -= 1

D[K] = 0
F[K] = False

L = [K]

while sum(F) > 0:
    L_tmp = []
    for k in L:
        for t in T[k]:
            b, c = t
            if F[b] == True:
                D[b] = D[k] + c
                F[b] = False
                L_tmp.append(b)
    L = L_tmp

for q 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:
# N 個の頂点、N-1 個の辺なので K を根にした木構造に変換する

N = int(input())
T = {}
D = [None] * N
F = [True] * N

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

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

K -= 1

D[K] = 0
F[K] = False

L = [K]

while sum(F) > 0:
    L_tmp = []
    for k in L:
        for t in T[k]:
            b, c = t
            if F[b] == True:
                D[b] = D[k] + c
                F[b] = False
                L_tmp.append(b)
    L = L_tmp

for q 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
sys.setrecursionlimit(10**7)
N = int(input())
G = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b, c = map(int, input().split())
    G[a].append((b, c))
    G[b].append((a, c))
Q, K = map(int, input().split())


d = [-1]*(N+1)


def dfs(v, c):
    d[v] = c
    for nv, cost in G[v]:
        if d[nv] == -1:
            dfs(nv, cost+c)

dfs(K, 0)

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

Submission status: Time Limit Exceeded

Solution code:
import heapq

n = int(input())
distance = [[float('inf')] * n for _ in range(n)]
for _ in range(n - 1):
    a, b, c = map(int, input().split())
    distance[a - 1][b - 1] = c
    distance[b - 1][a - 1] = c
q, k = map(int, input().split())
k -= 1
queries = []
for _ in range(q):
    x, y = map(int, input().split())
    queries.append((x - 1, y - 1))

d = [float('inf')] * (n + 1)
d[k] = 0
queue = [(0, k)]
while queue:
    cost, current = heapq.heappop(queue)
    for nxt in range(n):
        if cost + distance[current][nxt] < d[nxt]:
            d[nxt] = cost + distance[current][nxt]
            heapq.heappush(queue, (d[nxt], nxt))

for x, y in queries:
    print(d[x] + d[y])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

"""
参考：https://img.atcoder.jp/abc070/editorial.pdf
・公式解が再帰だったのでやってみる
"""

import sys

# 再帰呼び出しの回数制限(デフォルト1000)
sys.setrecursionlimit(10 ** 9)

from heapq import heappop, heappush

N = int(input())
nodes = [[] for _ in range(N+1)]
for i in range(N-1):
    a, b, c = map(int, input().split())
    # nodes[出発ノード](到着ノード, コスト))
    nodes[a].append((b, c))
    # 無向グラフなのでこっちも入れる
    nodes[b].append((a, c))

memo = [0] * (N+1)
def dfs(cur, prev, dist):
    memo[cur] = dist
    for nxt, cost in nodes[cur]:
        if nxt == prev:
            continue
        dfs(nxt, cur, dist+cost)

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

for i in range(Q):
    x, y = map(int, input().split())
    # 今回は全てKを経由するので、Kからの距離さえ分かれば全部出る
    print(memo[x] + memo[y])