Problem: 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.

Submission attempts (in order):
import heapq
n = int(f.readline())
cost = [[float('inf') for _ in range(n+1)] for _ in range(n+1)]
for _ in range(n-1):
    From, To, d = map(int, f.readline().split())
    cost[From][To] = d
    cost[To][From] = d

q, k = map(int, f.readline().split())
dist = [[float('inf') for _ in range(n+1)] for _ in range(n+1)]
used = [False]*(n+1)

for i in range(n+1):
    dist[i][i] = 0
        
def dijkstra(s, dist):
    next_v = [[0, s]]
    
    while len(next_v):
        v = next_v[0][1]
        for i in range(n+1):
            if dist[s][i] > dist[s][v] + cost[v][i]:
                dist[s][i] = dist[s][v] + cost[v][i]
                heapq.heappush(next_v, [dist[s][i], i])
        heapq.heappop(next_v)
        
    return dist
dist = dijkstra(k, dist)

for _ in range(q):
    x, y = map(int, f.readline().split())
    if used[x] == False:
        dist = dijkstra(x, dist)
        used[x] = True
    print(dist[x][k]+dist[k][y])

def dijkstra(n, edges, s):
    min_dist = [float('inf')] * n
    min_dist[s] = 0
    next_v = []
    heapq.heappush(next_v, (0, s))
    path = [-1] * n
    
    while True:
        if len(next_v) == 0: break
        d, v = heapq.heappop(next_v)
        
        for u, d in edges[v]:
            if min_dist[u] > min_dist[v] + d:
                min_dist[u] = min_dist[v] + d
                heapq.heappush(next_v, (min_dist[u], u))
                path[u] = v
                
    return min_dist, path

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

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

dist = [None] * n
for i in range(n):
    dist[i], _ = dijkstra(n, edges, i)

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

import heapq
n = int(input())
cost = [[float('inf') for _ in range(n+1)] for _ in range(n+1)]
for _ in range(n-1):
    From, To, d = map(int, input().split())
    cost[From][To] = d
    cost[To][From] = d

q, k = map(int, input().split())
dist = [[float('inf') for _ in range(n+1)] for _ in range(n+1)]
used = [False]*(n+1)

for i in range(n+1):
    dist[i][i] = 0
        
def dijkstra(s, dist):
    next_v = [[0, s]]
    
    while len(next_v):
        v = next_v[0][1]
        for i in range(n+1):
            if dist[s][i] > dist[s][v] + cost[v][i]:
                dist[s][i] = dist[s][v] + cost[v][i]
                heapq.heappush(next_v, [dist[s][i], i])
        heapq.heappop(next_v)
        
    return dist
dist = dijkstra(k, dist)

for _ in range(q):
    x, y = map(int, f.readline().split())
    if used[x] == False:
        dist = dijkstra(x, dist)
        used[x] = True
    print(dist[x][k]+dist[k][y])

import heapq
def dijkstra(n, edges, s):
    min_dist = [float('inf')] * n
    min_dist[s] = 0
    next_v = []
    heapq.heappush(next_v, (0, s))
    path = [-1] * n
    
    while True:
        if len(next_v) == 0: break
        d, v = heapq.heappop(next_v)
        
        for u, d in edges[v]:
            if min_dist[u] > min_dist[v] + d:
                min_dist[u] = min_dist[v] + d
                heapq.heappush(next_v, (min_dist[u], u))
                path[u] = v
                
    return min_dist, path

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

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


q, k = map(int, input().split())
dist, _ = dijkstra(n, edges, k-1)

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

Verdicts: Runtime Error

Runtime Error

Runtime Error

Accepted