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())
ds = [[0]*N for i in range(N)]
for i in range(N-1):
  a, b, c = list(map(int, input().split(" ")))
  ds[a-1][b-1] = c
  ds[b-1][a-1] = c
q, k = list(map(int, input().split(" ")))
 
def dfs(path, dist, c):
  if c==g:
    return dist
  dists = []
  for i in range(N):
    if ds[i][c]>0 and i not in path:
      dists.append(dfs(path+[c],dist+ds[i][c],i))
  if len(dists)>0:
	  return min(dists)
  else:
      return 10**15
 
ky = []
xk = []
for i in range(N):
  if i==k-1:
    ky.append(0)
    xk.append(0)
  else:
    g = i
    ky.append(dfs([],0,k-1))
    g = k-1
    xk.append(dfs([],0,i))
    
for i in range(q):
  x, y = list(map(int, input().split(" ")))
  print(xk[x-1]+ky[y-1])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
ds = [[0]*N for i in range(N)]
for i in range(N-1):
  a, b, c = list(map(int, input().split(" ")))
  ds[a-1][b-1] = c
  ds[b-1][a-1] = c
q, k = list(map(int, input().split(" ")))

def dfs(path, dist, c):
  if c==g:
    return dist
  dists = []
  for i in range(N):
    if ds[i][c]>0 and i not in path:
      dists.append(dfs(path+[c],dist+ds[i][c],i))
  if len(dists)>0:
	  return min(dists)
  else:
      return 10**15

ky = []
xk = []
for i in range(N):
  if i==k-1:
    ky.append(0)
    xk.append(0)
  else:
    g = i
    ky.append(dfs([],0,k-1))
    g = k-1
    xk.append(dfs([],0,i))
    
for i in range(q):
  x, y = list(map(int, input().split(" ")))
  print(xk[x-1]+ky[y-1])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
ds = [[0]*N for i in range(N)]
for i in range(N-1):
  a, b, c = list(map(int, input().split(" ")))
  ds[a-1][b-1] = c
  ds[b-1][a-1] = c
q, k = list(map(int, input().split(" ")))

def dfs(path, dist, c):
  if c==g:
    return dist
  dists = []
  for i in range(N):
    if ds[i][c]>0 and i not in path:
      dists.append(dfs(path+[c],dist+ds[i][c],i))
  if len(dists)>0:
	  return min(dists)
  else:
      return 10**15

ky = []
for i in range(N):
  if i==k-1:
    ky.append(0)
  else:
    g = i
    ky.append(dfs([],0,k-1))
    
for i in range(q):
  x, y = list(map(int, input().split(" ")))
  g = k-1
  d1 = dfs([], 0, x-1)
  print(d1+ky[y-1])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
ds = [[0]*N for i in range(N)]
for i in range(N-1):
  a, b, c = list(map(int, input().split(" ")))
  ds[a-1][b-1] = c
  ds[b-1][a-1] = c
q, k = list(map(int, input().split(" ")))

def dfs(path, dist, c):
  if c==g:
    return dist
  dists = []
  for i in range(N):
    if ds[i][c]>0 and i not in path:
      dists.append(dfs(path+[c],dist+ds[i][c],i))
  if len(dists)>0:
	  return min(dists)
  else:
      return 10**15

for i in range(q):
  x, y = list(map(int, input().split(" ")))
  g = k-1
  d1 = dfs([], 0, x-1)
  g = y-1
  d2 = dfs([], 0, k-1)
  print(d1+d2)

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(10**6)

@lru_cache(maxsize=1000)
def dfs(v,p,d):
    for i, j in tree[v]:
        if i != p:
            depth[i] = d + j
            dfs(i,v,d+j)

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

depth = [0 for i in range(N)]
depth[K-1] = 0

dfs(K-1,-1,0)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(10**6)

@lru_cache(maxsize=None)
def dfs(v,p,d):
    for i, j in tree[v]:
        if i != p:
            depth[i] = d + j
            dfs(i,v,d+j)

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

depth = [0 for i in range(N)]
depth[K-1] = 0

dfs(K-1,-1,0)

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

Submission status: Time Limit Exceeded

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

def dfs(v,p,d):
    for i, j in tree[v]:
        if i != p:
            depth[i] = d + j
            dfs(i,v,d+j)

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

depth = [0 for i in range(N)]
depth[K-1] = 0

dfs(K-1,-1,0)

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

Submission status: Time Limit Exceeded

Solution code:
def dijkstra(s,n,w,cost):
    d = [float('inf')] * n
    used = [False] * n
    d[s] = 0

    while True:
        v = -1
        for i in range(n):
            if (not used[i]) and (v == -1):
                v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
            break
        used[v] = True

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

N = int(input())

cost = [[float('inf')] * N for _ in range(N)]

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


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

Submission status: Time Limit Exceeded

Solution code:
def dijkstra(s,n,w,cost):
    d = [float('inf')] * n
    used = [False] * n
    d[s] = 0

    while True:
        v = -1
        for i in range(n):
            if (not used[i]) and (v == -1):
                v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
            break
        used[v] = True

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

N = int(input())

cost = [[float('inf')] * N for _ in range(N)]

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


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

Submission status: Time Limit Exceeded

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

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

checked = [False] * N

d = [INF] * N
d[K-1] = 0
def dijkstra(s):
    while True:
        v = -1
        for i in range(N):
            if checked[i] == False and v == -1:
                v = i
            elif checked[i] == False and d[i] < d[v]:
                v = i
        if v == -1:
            break
        
        checked[v] = True
        for i in range(N):
            d[i] = min(d[i], d[v] + es[v][i])
    return

dijkstra(K-1)

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

Submission status: Time Limit Exceeded

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

def main():
    N = int(input())
    X = [list(map(int,input().split())) for _ in range(N-1)]
    Q,K = map(int,input().split())
    Y = [list(map(int,input().split())) for _ in range(Q)]

    tree = [[] for _ in range(N)]
    dif = [10**15 for _ in range(N)]
    dif[K-1] = 0
    for i in range(N-1):
        tree[X[i][0]-1].append(X[i][1])
        tree[X[i][1]-1].append(X[i][0])

    queue = [K]
    while queue:
        a = queue.pop()
        for i in range(N-1):
            if X[i][0] == a:
                dif[X[i][1]-1] = min(dif[X[i][1]-1],dif[a-1]+X[i][2])
                tree[X[i][1]-1].remove(a)
                queue[0:0] = tree[a-1]
            if X[i][1] == a:
                dif[X[i][0]-1] = min(dif[X[i][0]-1],dif[a-1]+X[i][2])
                tree[X[i][0]-1].remove(a)
                queue[0:0] = tree[a-1]
        queue = list(set(queue))

    for i in range(Q):
        print(dif[Y[i][0]-1]+dif[Y[i][1]-1])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
inf = float('inf')

def solve(graph, n, start_node):
  costs = [inf for _ in range(n)]
  costs[start_node] = 0
  flgs = [False for _ in range(n)]

  while not all(flgs):
    prv_node = _get_min_idx(flgs,costs)
    flgs[prv_node] = True

    for node, dis in graph[prv_node]:
      if costs[node] > costs[prv_node] + dis:
        costs[node] = costs[prv_node] + dis 
  return costs
    
def _get_min_idx(flgs, costs):
    min_cost = inf
    min_idx = None
    cnt = 0
    for cost, flg in zip(costs, flgs):
      if min_cost > cost and flg is False:
        min_cost = cost
        min_idx = cnt
      cnt += 1
    return min_idx
        

n =int(input())
graph = defaultdict(list)
costs_dict = {}

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

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

costs = solve(graph, n, k)

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
inf = float('inf')

def solve(graph, n, start_node, end_node):
  if start_node == end_node:
    return 0

  global costs_dict
  key = str(start_node) + '-' + str(end_node)
  if key in costs_dict:
    return costs_dict[key][end_node]

  costs = [inf for _ in range(n)]
  costs[start_node] = 0
  flgs = [False for _ in range(n)]

  while not all(flgs):
    prv_node = _get_min_idx(flgs,costs)
    flgs[prv_node] = True

    for node, dis in graph[prv_node]:
      if costs[node] > costs[prv_node] + dis:
        costs[node] = costs[prv_node] + dis
  costs_dict[key] = costs  
  return costs[end_node]
    
    
def _get_min_idx(flgs, costs):
    min_cost = inf
    min_idx = None
    cnt = 0
    for cost, flg in zip(costs, flgs):
      if min_cost > cost and flg is False:
        min_cost = cost
        min_idx = cnt
      cnt += 1
    return min_idx
        

n =int(input())
graph = defaultdict(list)
costs_dict = {}

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

q, k = map(int, input().split())
k -= 1
for _ in range(q):
  x, y = map(int, input().split())
  print( solve(graph, n, x-1, k) + solve(graph, n, k, y-1))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
inf = float('inf')

def solve(graph, n, start_node, end_node):
  if start_node == end_node:
    return 0

  costs = [inf for _ in range(n)]
  costs[start_node] = 0
  flgs = [False for _ in range(n)]

  while not all(flgs):
    prv_node = _get_min_idx(flgs,costs)
    flgs[prv_node] = True

    for node, dis in graph[prv_node]:
      if costs[node] > costs[prv_node] + dis:
        costs[node] = costs[prv_node] + dis
  return costs[end_node]
    
    
def _get_min_idx(flgs, costs):
    min_cost = inf
    min_idx = None
    cnt = 0
    for cost, flg in zip(costs, flgs):
      if min_cost > cost and flg is False:
        min_cost = cost
        min_idx = cnt
      cnt += 1
    return min_idx
        

n =int(input())
graph = defaultdict(list)

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

q, k = map(int, input().split())
k -= 1
for _ in range(q):
  x, y = map(int, input().split())
  print( solve(graph, n, x-1, k) + solve(graph, n, k, y-1))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
inf = float('inf')

def solve(graph, n, start_node, end_node):
  costs = [inf for _ in range(n)]
  costs[start_node] = 0
  flgs = [False for _ in range(n)]

  while not all(flgs):
    prv_node = _get_min_idx(flgs,costs)
    flgs[prv_node] = True

    for node, dis in graph[prv_node]:
      if costs[node] > costs[prv_node] + dis:
        costs[node] = costs[prv_node] + dis
  return costs[end_node]
    
    
def _get_min_idx(flgs, costs):
    min_cost = inf
    min_idx = None
    cnt = 0
    for cost, flg in zip(costs, flgs):
      if min_cost > cost and flg is False:
        min_cost = cost
        min_idx = cnt
      cnt += 1
    return min_idx
        

n =int(input())
graph = defaultdict(list)

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

q, k = map(int, input().split())
k -= 1
for _ in range(q):
  x, y = map(int, input().split())
  print( solve(graph, n, x-1, k) + solve(graph, n, k, y-1))

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import lil_matrix, csr_matrix
N = int(input())
L = [[0 for _ in range(N)] for _ in range(N)]
for i in range(N-1):
  a, b, c = map(int, input().split())
  L[a-1][b-1] = c
  L[b-1][a-1] = c
L = csr_matrix(L)
L = floyd_warshall(L, 0)
Q, K = map(int, input().split())
K -= 1
for i in range(Q):
  x, y = map(int, input().split())
  x -= 1
  y -= 1
  print (int(L[x][K] + L[K][y]))

Submission status: Time Limit Exceeded

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

n=int(input())
l=[list(map(int,input().split())) for _ in [0]*(n-1)]
q,k=map(int,input().split())
L=[list(map(int,input().split())) for _ in [0]*q]

cost=[-1]*(n+1)
cost[k]=0
c=0
while c<n-1:
    for i in range(n-1):
        if cost[l[i][0]]!=-1 and cost[l[i][1]]==-1:
            cost[l[i][1]]=cost[l[i][0]]+l[i][2]
            c+=1
        if cost[l[i][1]]!=-1 and cost[l[i][0]]==-1:
            cost[l[i][0]]=cost[l[i][1]]+l[i][2]
            c+=1
for i in range(q):
    print(cost[L[i][0]]+cost[L[i][1]])

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import floyd_warshall
n=int(input())
s=[[0]*n for _ in range(n)]
for i in range(n-1):
    a,b,c=map(int,input().split())
    s[a-1][b-1]=c
    s[b-1][a-1]=c
s=floyd_warshall(s)

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

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)] 
#cost[u][v] : 辺uvのコスト(存在しないときはinf この場合は10**10)
for i in range(n-1):
    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())
dks=dijkstra(k-1,n,n-1,cost)
for i in range(q):
    a,b=map(int,input().split())
    print(dks[a-1]+dks[b-1])

Submission status: Time Limit Exceeded

Solution code:
def warshall_floyd(d):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

n=int(input())
d = [[float("inf") for i in range(n)] for i in range(n)] 
for i in range(n-1):
    x,y,z = map(int,input().split())
    d[x-1][y-1] = z
    d[y-1][x-1] = z
for i in range(n):
    d[i][i] = 0
wf=warshall_floyd(d)
q,k=map(int,input().split())
for i in range(q):
    a,b=map(int,input().split())
    print(wf[a-1][k-1]+wf[k-1][b-1])

Submission status: Time Limit Exceeded

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

input = sys.stdin.readline
N = int(input())

P=set()
for _ in range(N - 1):
  a, b, c = map(int, input().split())
  P.add((c, a - 1, b - 1))

d, i, j = zip(*P)
G = coo_matrix((d, (i, j)),(N, N)).tocsc()

Q, K = map(int, input().split())
P = dijkstra(G, indices=K - 1, directed=False)
for _ in range(Q):
  x, y = map(int, input().split())
  print(int(P[x - 1] + P[y - 1]))

Submission status: Time Limit Exceeded

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

input = sys.stdin.readline
N = int(input())

P=set()
for _ in range(N - 1):
  a, b, c = map(int, input().split())
  P.add((c, a - 1, b - 1))

d, i, j = zip(*P)
G = coo_matrix((d, (i, j)),(N, N))

Q, K = map(int, input().split())
P = dijkstra(G, indices=K - 1, directed=False)
for _ in range(Q):
  x, y = map(int, input().split())
  print(int(P[x - 1] + P[y - 1]))

Submission status: Time Limit Exceeded

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

input = sys.stdin.readline
N = int(input())

P=set()
for _ in range(N - 1):
  a, b, c = map(int, input().split())
  P.add((c, a - 1, b - 1))

d, i, j = zip(*P)
G = csc_matrix((d, (i, j)),(N, N))

Q, K = map(int, input().split())
P = dijkstra(G, indices=K - 1, directed=False)
for _ in range(Q):
  x, y = map(int, input().split())
  print(int(P[x - 1] + P[y - 1]))

Submission status: Time Limit Exceeded

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

input = sys.stdin.readline
N = int(input())

P=set()
for _ in range(N - 1):
  a, b, c = map(int, input().split())
  P.add((c, a - 1, b - 1))

d, i, j = zip(*P)
G = csr_matrix((d, (i, j)),(N, N))

Q, K = map(int, input().split())
P = dijkstra(G, indices=K - 1, directed=False)
for _ in range(Q):
  x, y = map(int, input().split())
  print(int(P[x - 1] + P[y - 1]))

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

N = int(input())

P=set()
for _ in range(N - 1):
  a, b, c = map(int, input().split())
  P.add((c, a - 1, b - 1))

d, i, j = zip(*P)
G = csr_matrix((d, (i, j)),(N, N))

Q, K = map(int, input().split())
P = dijkstra(G, indices=K - 1, directed=False)
for _ in range(Q):
  x, y = map(int, input().split())
  print(int(P[x - 1] + P[y - 1]))

Submission status: Time Limit Exceeded

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

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

Q, K = map(int, input().split())
P = dijkstra(G, indices=K - 1, directed=False)
for _ in range(Q):
  x, y = map(int, input().split())
  print(int(P[x - 1] + P[y - 1]))

Submission status: Time Limit Exceeded

Solution code:
#D問題
N = int(input())
inf = float("inf")
AB = [[inf for i in range(N)] for j in range(N)]
for i in range(N-1):
    a,b,c = map(int,input().split())
    AB[a-1][b-1] = c
    AB[b-1][a-1] = c
    
Q,K = map(int,input().split())
XY = [list(map(int,input().split())) for i in range(Q)]

inf = float("inf")
Dist = [inf for i in range(N)]
#DFS
def DFS(v,p,d):
    global Dist
    global AB
    Dist[v] = d
    for i in range(N):
        if Dist[i] == inf and AB[i][v] != inf:
            if i == p:
                pass
            else:
                DFS(i,v,d+AB[i][v])
    return
DFS(K-1,-1,0)

for i in range(Q):
    x = XY[i][0]-1
    y = XY[i][1]-1
    print(Dist[x]+Dist[y])

Submission status: Time Limit Exceeded

Solution code:
#D問題
#dijkstra法
import heapq

class Dijkstra(object):
    def dijkstra(self, adj, start, goal=None):
        num = len(adj)          # グラフのノード数
        dist = [float('inf') for i in range(num)] # 始点から各頂点までの最短距離を格納する
        prev = [float('inf') for i in range(num)] # 最短経路における，その頂点の前の頂点のIDを格納する
        
        dist[start] = 0
        q = []                  # プライオリティキュー．各要素は，(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル
        heapq.heappush(q, (0, start)) # 始点をpush

        while len(q) != 0:
            prov_cost, src = heapq.heappop(q) # pop
            
            # プライオリティキューに格納されている最短距離が，現在計算できている最短距離より大きければ，distの更新をする必要はない
            if dist[src] < prov_cost:
                continue

            # 他の頂点の探索
            for dest in range(num):
                cost = adj[src][dest]
                if cost != float('inf') and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost # distの更新
                    heapq.heappush(q, (dist[dest], dest)) # キューに新たな仮の距離の情報をpush
                    prev[dest] = src                      # 前の頂点を記録
                    
        if goal is not None:
            return self.get_path(goal, prev)
        else:
            return dist

    def get_path(self, goal, prev):
        '''
        始点startから終点goalまでの最短経路を求める
        '''
        path = [goal]           # 最短経路
        dest = goal

        # 終点から最短経路を逆順に辿る
        while prev[dest] != float('inf'):
            path.append(prev[dest])
            dest = prev[dest]

        # 経路をreverseして出力
        return list(reversed(path))



N = int(input())
inf = float("inf")
AB = [[inf for i in range(N)] for j in range(N)]
for i in range(N-1):
    a,b,c = map(int,input().split())
    AB[a-1][b-1] = c
    AB[b-1][a-1] = c
    
Q,K = map(int,input().split())
XY = [list(map(int,input().split())) for i in range(Q)]

D = Dijkstra()
Dist = D.dijkstra(AB,K-1)

for i in range(Q):
    x = XY[i][0]-1
    y = XY[i][1]-1
    print(Dist[x]+Dist[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 = [[0] * N for _ in range(N)]
for a, b, c in ABC:
  G[a - 1][b - 1] = c
  G[b - 1][a - 1] = c

D = [-1] * N
D[K - 1] = 0

q = deque()
q.append(K - 1)
while q:
  n = q.popleft()
  for i in range(N):
    if G[n][i] != 0 and D[i] < 0:
      q.append(i)
      D[i] = D[n] + G[n][i]

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#ABC70 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7

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)]
cost = [[float('inf')]*n for _ in range(n)]
for a,b,c in abc:
    g[a-1].append(b-1)
    g[b-1].append(a-1)
    cost[a-1][b-1] = c
    cost[b-1][a-1] = c

que = deque()
que.append((0,k-1))
c = [False]*n
dist = [float('inf')]*n
while que:
    d,v = que.popleft()
    dist[v] = min(dist[v],d)
    if not c[v]:
        c[v] = True
        for u in g[v]:
            que.append((d+cost[v][u],u))
for _ in range(q):
    x,y = map(int,input().split())
    print(dist[x-1] + dist[y-1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#ABC70 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7

n = int(input())
abc = [list(map(int,input().split())) for _ in range(n-1)]
q,k = map(int,input().split())

cost = [[float('inf')]*n for _ in range(n)]
for a,b,c in abc:
    cost[a-1][b-1] = c
    cost[b-1][a-1] = c

def dijkstra(start,num_v,cost):
    d = [float('inf')]*n
    used = [False]*n
    d[start] = 0

    while 1:
        v = -1
        for i in range(num_v):
            if not used[i] and v == -1:
                v = i
            elif not used[i] and d[i] < d[v]:
                v = i
        if v == -1:
            break
        used[v] = True

        for j in range(n):
            d[j] = min(d[j],d[v] + cost[v][j])
    return d
d = dijkstra(k-1,n,cost)
for _ in range(q):
    x,y = map(int,input().split())
    print(d[x-1] + d[y-1])

Submission status: Time Limit Exceeded

Solution code:
import queue

N = int(input())
E = {n: set() for n in range(N)}

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

Q, K = map(int, input().split())
K -= 1
dist = [-1] * N
already = set()
que = queue.Queue()
que.put((K, 0))
while not que.empty():
    now, d = que.get()
    already.add(now)
    dist[now] = d
    out = E[now]
    for n, c in out:
        if n in already:
            continue
        que.put((n, d + c))

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

Submission status: Time Limit Exceeded

Solution code:
import queue

N = int(input())
E = {n: set() for n in range(N)}
C = {}

for _ in range(N - 1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    E[a].add(b)
    E[b].add(a)
    C[(min(a, b), max(a, b))] = c 

Q, K = map(int, input().split())
K -= 1
dist = [-1] * N
already = set()
que = queue.Queue()
que.put((K, 0))
while not que.empty():
    now, c = que.get()
    already.add(now)
    dist[now] = c
    out = E[now]
    for n in out:
        if n in already:
            continue
        que.put((n, c + C[min(now, n), max(now, n)]))

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
route = {i + 1 : {} for i in range(n)}
for i in range(n - 1):
    a, b, c = map(int, input().split())
    route[a][b] = c
    route[b][a] = c
q, k = map(int, input().split())
queue = [k]
length = [0] * (n + 1)
while queue:
    search = queue.pop(0)
    pairs = []
    for i, j in route[search].items():
        queue.append(i)
        length[i] = length[search] + j
        pairs.append([search, i])
    for i, j in pairs:
        del route[i][j]
        del route[j][i]
for i in range(q):
    x, y = map(int, input().split())
    print(length[x] + length[y])

Submission status: Time Limit Exceeded

Solution code:
## abc070d: Transit Tree Path

n = int(input())

T = [None]*(n+1)
for _ in range(n-1):
    v1,v2,d = map(int, input().split())
    T[v1] = T[v1] + [[v1,v2,d]] if(T[v1]) else [[v1,v2,d]]
    T[v2] = T[v2] + [[v2,v1,d]] if(T[v2]) else [[v2,v1,d]]

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

depth = [0]*(n+1)
visit = [False]*(n+1)
depth[k] = 0
visit[k] = True
stack = T[k]
while stack:
    p,c,d = stack.pop()
    if visit[c]: continue
    visit[c] = True
    depth[c] = depth[p] + d
    for pp,cc,dd in T[c]:
        if not visit[cc]: stack.append([pp,cc,dd])

for _ in range(q):
    v1,v2 = map(int, input().split())
    print(depth[v1]+depth[v2])

Submission status: Time Limit Exceeded

Solution code:
## abc070d: Transit Tree Path

n = int(input())

T = [None]*(n+1)
for _ in range(n-1):
    v1,v2,d = map(int, input().split())
    T[v1] = T[v1] + [[v1,v2,d]] if(T[v1]) else [[v1,v2,d]]
    T[v2] = T[v2] + [[v2,v1,d]] if(T[v2]) else [[v2,v1,d]]

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

visit = [False]*(n+1)
depth = [0]*(n+1)
stack = [[0,k,0]]
while stack:
    p,c,d = stack.pop()
    if visit[c]: continue
    visit[c] = True
    depth[c] = depth[p] + d
    for pp,cc,dd in T[c]:
        if not visit[cc]: stack.append([pp,cc,dd])

for _ in range(q):
    v1,v2 = map(int, input().split())
    print(depth[v1]+depth[v2])

Submission status: Time Limit Exceeded

Solution code:
import collections
import sys

sys.setrecursionlimit(10000000)


stack = collections.deque()

N = int(input())
a = [-1] * (N-1)
b = [-1] * (N-1)
c = [-1] * (N-1)
cost = [0] * (N+1)
nodes = [[] for _ in range(N+1)]
yet = [int(ele) for ele in range(1, N+1)]

for i in range(N-1):
    a[i], b[i], c[i] = [int(ele) for ele in input().split()]  # 無効グラフなので、逆にも
    nodes[a[i]].append([b[i], c[i]])
    nodes[b[i]].append([a[i], c[i]])

Q, K = [int(ele) for ele in input().split()]
x = [-1] * Q
y = [-1] * Q

for i in range(Q):
    x[i], y[i] = [int(ele) for ele in input().split()]


def main():
    root = K
    stack.appendleft(root)
    bfs()

    for x_i, y_i in zip(x, y):
        print(cost[x_i] + cost[y_i])


def bfs():
    if len(stack) == 0:
        return

    parent = stack[-1]
    yet.remove(parent)
    for child in nodes[parent]:
        if child[0] in yet:
            stack.appendleft(child[0])
            cost[child[0]] = cost[parent] + child[1]
    else:
        stack.pop()
        bfs()


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)

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

visited = [-1] * N
ans = 0

maze_hash = {}
#繋がっている点をハッシュで表現する
for i in maze:
    if (i[0] - 1) in maze_hash:
        maze_hash[i[0] - 1].append([i[1] - 1, i[2]])
    else:
        maze_hash[i[0] - 1] = [[i[1] - 1, i[2]]]
    if (i[1] - 1) in maze_hash:
        maze_hash[i[1] - 1].append([i[0] - 1, i[2]])
    else:
        maze_hash[i[1] - 1] = [[i[0] - 1, i[2]]]

def dfs(now, goal, visiterd, ans):
    if visited[now] == -1:
        visited[now] = ans
    else:
        visited[now] = min(visited[now], ans)
    if now == goal:
        return ans
    #次に行けるところを探す。
    tmp = 10000000000000000000
    for i in maze_hash[now]:
        if visited[i[0]] == -1:
           tmp = min(tmp, dfs(i[0], goal, visited, ans + i[1]))
    return tmp


to_k_list = [0] * N

for i in range(N):
    visited = [-1] * N
    ans = 0
    to_k_list[i] = dfs(i, K - 1, visited, 0)


to_goal_list = [0] * N
for i in range(N):
    visited = [-1] * N
    to_goal_list[i] = dfs(K - 1, i, visited, 0)


#まずx から　K への経路を計算しておく。
for i in query:
    print(to_k_list[i[0] - 1] + to_goal_list[i[1] - 1])