TnT/Multi_CodeNet4Repair huggingface dataset:
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):
n = int(input())
graph = [[] for _ in range(n)]
for _ in range(n-1):
  a, b, c = map(int, input().split())
  a-=1
  b-=1
  graph[a].append((b, c))
  graph[b].append((a, c))
q, k = map(int, input().split())
k-=1
seen = [False]*n
l = [0]*n

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

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

def DFS(node, p_node, length):
    l[node] = length
    for i, j in graph[node]:
        if i==p_node:
            continue
        DFS(i, node, length+j)
sys.setrecursionlimit(2 * N)
l = [0]*n
DFS(k, -1, 0)
for x, y in xy:
    print(l[x]+l[y])


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

l = [0]*(n+1)
def DFS(node, p_node, length):
  l[node] = length
  for i, j in graph[node]:
    if i==p_node:
      continue
    DFS(i, node, length+j)
DFS(k, -1, 0)
for x, y in xy:
  print(0)

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

def DFS(node, p_node, length):
    l[node] = length
    for i, j in graph[node]:
        if i==p_node:
            continue
        DFS(i, node, length+j)
sys.setrecursionlimit(2 * n)
l = [0]*n
DFS(k, -1, 0)
for x, y in xy:
    print(l[x]+l[y])


Verdicts: Wrong Answer

Runtime Error

Runtime Error

Accepted
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):
#include <bits/stdc++.h>

using namespace std;

const int N = 100005;

long long d[N];
vector<pair<int, int>> g[N];

void dfs(int u, int f, long long w) {
  d[u] = w;
  for (auto &go : g[u]) {
    if (go.first != f) {
      dfs(go.first, u, w + go.second);
    }
  }
}

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i < n; ++i) {
    int u, v, w;
    scanf("%d %d %d", &u, &v, &w);
    g[u].push_back({v, w});
    g[v].push_back({u, w});
  }
  int q, k;
  scanf("%d %d", &q, &k);
  dfs(k, k, 0);
  while (q--) {
    int u, v;
    scanf("%d %d", &u, &v);
    cout << d[u] + d[v] << endl;
  }
  return 0;
}


n = int(input())
g = []
d = [0] * (n + 1)
for i in range(n + 1):
    g.append([]);
for i in range(n - 1):
    u, v, w = map(int, input().split())
    g[u].append([v, w])
    g[v].append([u, w])
q, k = map(int, input().split())
def bfs(u):
    s = []
    s.append(u)
    while s:
        v = s[-1]
        s.pop()
        for go in g[v]:
            if not d[go[0]] and go[0] != u:
                d[go[0]] = d[v] + go[1]
                s.append(go[0])
bfs(k)
while q > 0:
    u, v = map(int, input().split())
    print(d[u] + d[v])
    q -= 1


Verdicts: Runtime Error

Accepted
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 numpy as np
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix
N = int(input())
L = np.full((N, N), np.inf)
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)
print (L)
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]))

from collections import defaultdict as dd
from collections import deque
N = int(input())
D =dd(list)
for i in range(N-1):
  a, b, c = map(int, input().split())
  D[a-1].append((b-1, c))
  D[b-1].append((a-1, c))

Q, K = map(int, input().split())
K -= 1
L = [0 for _ in range(N)]
q = deque([])
q.append(K)
while len(q) > 0:
  a = q.pop()
  for b, c in D[a]:
    if L[b] == 0:
      L[b] = L[a] + c
      q.append(b)

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

Verdicts: Runtime Error

Accepted
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):
#from numpy import*
from scipy.sparse.csgraph import shortest_path
from scipy.sparse import csr_matrix

from collections import* 
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul
from bisect import* 
from heapq import* 
from math import factorial,pi
from copy import deepcopy
import sys

sys.setrecursionlimit(10**6)

def main():
    n=int(input())
    graph=[[0]*n for i in range(n)]
    for i in range(n-1):
        a,b,c=map(int,input().split())
        graph[a-1][b-1]=c
        graph[b-1][a-1]=c
    graph=csr_matrix(graph)
    d = shortest_path(csgraph=graph)
    q,k=map(int,input().split())
    for i in range(q):
        a,b=map(int,input().split())
        print(int(d[a-1][k-1]+d[k-1][b-1]))
if __name__ == '__main__':
    main()


from collections import*
from heapq import*
import sys
input=sys.stdin.readline
 
def BFS(point,d):
    cost=[1e18]*(n+1)
    cost[point]=0
    Q=deque()
    Q.appendleft((0,point))
    
    while Q:
        c,p=Q.pop()
        for np,co in d[p]:
            if cost[np]==1e18:
                cost[np]=c+co
                Q.appendleft((c+co,np))
    return cost

n=int(input())
d=[[]for i in range(n+1)]
for i in range(n-1):
    a,b,c=map(int,input().split())
    d[a].append([b,c])
    d[b].append([a,c])
#print(d)
q,k=map(int,input().split())
y=BFS(k,d)
 
for i in range(q):
    a,b=map(int,input().split())
    print(y[a]+y[b])


Verdicts: Runtime Error

Accepted
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):
from collections import defaultdict
def inpl(): return [int(i) for i in input().split()]

path = defaultdict(lambda: [])
N = int(input())
for _ in range(N-1):
    a, b, c = inpl()
    path[a].append((b,c))
    path[b].append((a,c))

ctr = 1
Q, K = inpl()
now = [K]
dist = [0 for _ in range(N+1)]
while True:
    for na in now.copy():
        na = now.pop()
        for nb, nc in path[na]:
            dist[nb] = dist[na] + nc
            path[nb].remove((na,nc))
            now.add(nb)
            ctr += 1
    if ctr >=  N:
        break
for i in range(Q):
    x, y = inpl()
    print(dist[x]+dist[y])

from collections import defaultdict
def inpl(): return [int(i) for i in input().split()]

path = defaultdict(lambda: [])
N = int(input())
for _ in range(N-1):
    a, b, c = inpl()
    path[a].append((b,c))
    path[b].append((a,c))

ctr = 1
Q, K = inpl()
now = {K}
dist = [0 for _ in range(N+1)]
while True:
    for na in now.copy():
        na = now.pop()
        for nb, nc in path[na]:
            dist[nb] = dist[na] + nc
            path[nb].remove((na,nc))
            now.add(nb)
            ctr += 1
    if ctr >=  N:
        break
for i in range(Q):
    x, y = inpl()
    print(dist[x]+dist[y])

Verdicts: Runtime Error

Accepted
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 sys
sys.setrecursionlimit(10**6);l=lambda:map(int, input().split());n=int(input()):s=[0for _ in[0]*n];j=[[]for _ in[0]*n]
for _ in range(n-1):a,b,c=l();j[a-1].append([b-1,c]);j[b-1].append([a-1,c])
def f(v,p,d):
 s[v]=d
 for i,c in j[v]:
  if i==p:
   continue
  f(i,v,d+c)
q,k=l()
dfs(k-1,-1,0)
for _ in [0]*q:x,y=l();print(s[x-1]+s[y-1])

import sys
sys.setrecursionlimit(10**6);l=lambda:map(int, input().split());n=int(input());s=[0for _ in[0]*n];j=[[]for _ in[0]*n]
for _ in range(n-1):a,b,c=l();j[a-1].append([b-1,c]);j[b-1].append([a-1,c])
def f(v,p,d):
 s[v]=d
 for i,c in j[v]:
  if i==p:
   continue
  f(i,v,d+c)
q,k=l()
dfs(k-1,-1,0)
for _ in [0]*q:x,y=l();print(s[x-1]+s[y-1])

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n = int(input())

dis = [ 0 for _ in range(n)]  
adj = [[] for _ in range(n)] 

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




def dfs(v, p, d):
    dis[v] = d
    for i, c in adj[v]:
        if i == p:
            continue
        dfs(i, v, d+c)

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

dfs(k, -1, 0)

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

Verdicts: Runtime Error

Runtime Error

Accepted
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):
N = int(input())
edges = []
connected = [[] for i in range(N+1)]
for i in range(N-1):
    x=list(map(int, input().split()))
    x[0] -= 1
    x[1] -= 1
    edges.append(x)
    connected[x[0]].append([x[1], x[2]])
    connected[x[1]].append([x[0], x[2]])

Q,K = map(int, input().split())
depth = [0]*N
def DFS(v, p, d):
    depth[v] = d
    for child in connected[v]:
        if child[0] == p:
            continue
        DFS(child[0], v, d+child[1])

DFS(K,-1,0)
for i in range(Q):
    xi, yi = map(int, input().split())
    print(depth[xi-1]+depth[yi-1])

    


import sys
sys.setrecursionlimit(200000)

N = int(input())
edges = []
connected = [[] for i in range(100010)]
for i in range(N-1):
    x=list(map(int, input().split()))
    x[0] -= 1
    x[1] -= 1
    edges.append(x)
    connected[x[0]].append([x[1], x[2]])
    connected[x[1]].append([x[0], x[2]])

Q,K = map(int, input().split())
K -= 1
depth = [0]*100010
def DFS(v, p, d):
    depth[v] = d
    for child in connected[v]:
        if child[0] == p:
            continue
        DFS(child[0], v, d+child[1])

DFS(K,-1,0)
for i in range(Q):
    xi, yi = map(int, input().split())
    print(depth[xi-1]+depth[yi-1])


Verdicts: Runtime Error

Accepted
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):
from collections import defaultdict

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

for i in range(n-1):
  a,b,c=map(int,input().split())
  dct[a]+=[[b,c]]
  dct[b]+=[[a,c]]
print(dct)

q,k=map(int,input().split())
lk=[0]*(n)

def dfs(v,p,d):
  lk[v-1]=d
  print(k,v,p,d,lk)
  for l in dct[v]:
    if l[0]==p:
      continue
    else:
      dfs(l[0],v,d+l[1])
  return

dfs(k,-1,0)

print(lk)

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

from collections import defaultdict
import sys
sys.setrecursionlimit(10**9)

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

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


q,k=map(int,input().split())
lk=[0]*(n)

def dfs(v,p,d):
  lk[v-1]=d

  for l in dct[v]:
    if l[0]==p or lk[l[0]-1]!=0:
      continue
    else:
      dfs(l[0],v,d+l[1])
  return

dfs(k,-1,0)



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


Verdicts: Runtime Error

Accepted
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(input())
edges = []
for i in range(N-1):
    a, b, c = map(int, input().split())
    edges.append([a-1, b-1, c])
    edges.append([b-1, a-1, c])
Q, K = map(int, input().split())
K -= 1


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

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

for i in ans_list:
    print(i)

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


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

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

for i in ans_list:
    print(i)

Verdicts: Wrong Answer

Accepted
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):
N = int(input())

class Edge:
    def __init__(self,to,cost):
        self.to = to
        self.cost = cost

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

def dfs(s,pare):
    for i in graph[s]:
        if i.to != pare :
            dp[i.to] = dp[s] + i.cost
            dfs(i.to,s)


Q,K = map(int,input().split())
dfs(K-1,-1)
print(dp)
for i in range(Q):
    x,y = map(int,input().split())
    print("{}".format(dp[x-1]+dp[y-1]))

import sys
sys.setrecursionlimit(10**9)
N = int(input())

class Edge:
    def __init__(self,to,cost):
        self.to = to
        self.cost = cost

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

def dfs(s,pare):
    for i in graph[s]:
        if i.to != pare :
            dp[i.to] = dp[s] + i.cost
            dfs(i.to,s)
        else:
            continue 


Q,K = map(int,input().split())
dfs(K-1,-1)
for i in range(Q):
    x,y = map(int,input().split())
    print("{}".format(dp[x-1]+dp[y-1]))


Verdicts: Runtime Error

Accepted
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):
N = int(input())
T = [{} for i in range(N+1)]
for _ in range(N-1):
    a, b, c = map(int, input().split())
    T[a][b] = c
    T[b][a] = c

Q, K = map(int, input().split())
shortest_path = [0 for _ in range(N+1)]
queue = [[v, T[K][v], K] for v in T[K].keys()]

for _ in range(N-1):
    v = queue.pop(0)
    shortest_path[v[0]] = v[1]
    queue += [[u, T[v[0]][u] + v[1], v[0]] for u in T[v[0]].keys() if u != v[2]]

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

Q, K = map(int, input().split())
shortest_path = [0 for _ in range(N+1)]
queue = [[v, T[K][v], K] for v in T[K].keys()]
for _ in range(N-1):
    v, c, p = iter(queue.pop(0))
    shortest_path[v] = c
    queue += [[u, T[v][u] + c, v] for u in T[v].keys() if u != p]

from collections import deque

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

Q, K = map(int, input().split())
shortest_path = [0 for _ in range(N+1)]
queue = deque([[v, T[K][v], K] for v in T[K].keys()])
for _ in range(N-1):
    v = queue.popleft()
    shortest_path[v[0]] = v[1]
    queue.extend([[u, T[v[0]][u] + v[1], v[0]] for u in T[v[0]].keys() if u != v[2]])

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

Verdicts: Wrong Answer

Wrong Answer

Accepted
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):
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

sys.setrecursionlimit(10**5 + 5)

N = int(input())

g = {i: [] for i in range(1, 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())
xy = []
for _ in range(Q):
    xy.append(tuple(map(int, input().split())))

d = [-1 for _ in range(N+1)]


def dfs(s: int):
    for v, c in g[s]:
        if d[v] == -1:
            d[v] = d[s] + c
            dfs(v)


d[K] = 0
dfs(K)

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


sys.setrecursionlimit(10000)

N = int(input())

edges = {n: [] for n in range(N+1)}

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

    edges[a].append((b, c))
    edges[b].append((a, c))

Q, K = map(int, input().split())
xy = []
for _ in range(Q):
    xy.append(tuple(map(int, input().split())))


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


def dfs(n: int):
    for m, c in edges[n]:
        if d[m] == -1:
            d[m] = d[n] + c
            dfs(m)


dfs(K)

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


import sys
sys.setrecursionlimit(10**5 + 5)

N = int(input())

g = {i: [] for i in range(1, 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())
xy = []
for _ in range(Q):
    xy.append(tuple(map(int, input().split())))

d = [-1 for _ in range(N+1)]


def dfs(s: int):
    for v, c in g[s]:
        if d[v] == -1:
            d[v] = d[s] + c
            dfs(v)


d[K] = 0
dfs(K)

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

Verdicts: Runtime Error

Runtime Error

Runtime Error

Accepted
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):
# coding=utf-8

N = int(input())
tree = [[]for x in range(N)]
depth = [0 for x in range(N)]
for _ in range(N-1):
    line = input().split(" ")
    a = int(line[0])-1
    b = int(line[1])-1
    c = int(line[2])
    tree[a].append((b, c))
    tree[b].append((a, c))

line = input().split(" ")
Q = int(line[0])
K = int(line[1])-1

def dfs(v, p, d):
    depth[v] = d
    for e in tree[v]:
        if e[0]==p:
            continue
        dfs(e[0], v, d+e[1])

dfs(K, -1, 0)

for _ in range(Q):
    line = input(" ").split(" ")
    x = int(line[0])-1
    y = int(line[1])-1
    print(str(depth[x]+depth[y]))


# -*- coding: utf-8 -*-
inf = 10**16
n = int(input())
edge = [[] for _ in range(n)]
for _ in range(n-1):
    a,b,c = map(int, input().split())
    a -= 1
    b -= 1
    edge[a].append((b,c))
    edge[b].append((a,c))

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

d = [inf for _ in range(n)]
d[k] = 0
stack = [k]
while len(stack)>0:
    v = stack.pop()
    for u,c in edge[v]:
        if d[u]==inf:
            d[u] = d[v]+c
            stack.append(u)

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

for c in res:
    print(c)


Verdicts: Runtime Error

Accepted
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 sys
sys.setrecursionlimit(10 ** 10)


class Solve():
    def __init__(self):
        self.N = int(input())
        self.route = [dict() for _ in range(self.N)]
        for _ in range(self.N - 1):
            a, b, c = map(int, input().split())
            self.route[a - 1][b - 1] = c
            self.route[b - 1][a - 1] = c
        self.Q, self.K = map(int, input().split())
        self.K -= 1
        self.query = []
        for _ in range(self.Q):
            x, y = map(int, input().split())
            self.query.append([x - 1, y - 1])
        self.depth = [0 for _ in range(self.N)]

    def DFS(self, v, p, d):
        self.depth[v] = d
        for dest, cost in self.route[v].items():
            if dest == p:
                continue
            self.DFS(dest, v, d + cost)

    def execute(self):
        self.DFS(self.K, -1, 0)
        for x, y in self.query:
            print(self.depth[x] + self.depth[y])


if __name__ == '__main__':
    Solve().execute()

import sys
sys.setrecursionlimit(10 ** 8)


class Solve():
    def __init__(self):
        self.N = int(input())
        self.route = [dict() for _ in range(self.N)]
        for _ in range(self.N - 1):
            a, b, c = map(int, input().split())
            self.route[a - 1][b - 1] = c
            self.route[b - 1][a - 1] = c
        self.Q, self.K = map(int, input().split())
        self.K -= 1
        self.query = []
        for _ in range(self.Q):
            x, y = map(int, input().split())
            self.query.append([x - 1, y - 1])
        self.depth = [0 for _ in range(self.N)]

    def DFS(self, v, p, d):
        self.depth[v] = d
        for dest, cost in self.route[v].items():
            if dest == p:
                continue
            self.DFS(dest, v, d + cost)

    def execute(self):
        self.DFS(self.K, -1, 0)
        for x, y in self.query:
            print(self.depth[x] + self.depth[y])


if __name__ == '__main__':
    Solve().execute()

Verdicts: Runtime Error

Accepted
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):
from collections import deque 

n = int(input())

preroots = []
preroots_appd = preroots.append

for i in range(n-1):
    preroots_appd(list(map(int,input().split())))
    
roots = [[] for x in range(n+1)]

for i in preroots:
    roots[i[0]].append((i[1],i[2]))         
    roots[i[1]].append((i[0],i[2]))     
         
QK = list(map(int,input().split()))         
query = []

query_appd = query.append
for i in range(QK[0]):
    query_appd(list(map(int,input().split())))
        
    
distfrom_K = [-1 for x in range(n+1)]
distfrom_K[QK[1]] = 0          

q = deque()
q.append(QK[1])

while(len(q)):
    currentNode = q.popleft()
    for i in roots[currentNode]:
        if distfrom_K[i[0]] != -1:continue
        q.append(i[0])
        distfrom_K[i[0]] = distfrom_K[currentNode] + i[0]

for i in query:
    print(distfrom_K[i[0]]+distfrom_K[i[1]])

from collections import deque

n = int(input())
preroots = []
for i in range(n-1):    
    preroots.append(list(map(int,input().split())))

roots = [[] for i in range(n+1)]

for i in range(n-1):
    roots[preroots[i][0]].append([preroots[i][1],preroots[i][2]])
    roots[preroots[i][1]].append([preroots[i][0],preroots[i][2]])



QK = list(map(int,input().split()))
dist  = [-1 for i in range(n+1)]
dist[QK[1]] = 0
query = []
for i in range(QK[0]):
    query.append(list(map(int,input().split())))

q = deque()
q.append(QK[1])

while(len(q)):
    curr = q.popleft()
    for i in roots[curr]:
        if dist[i[0]] != -1:continue
        dist[i[0]] = dist[curr] + i[1]
        q.append(i[0])
        
for i in query:
    print(dist[i[0]] + dist[i[1]])

Verdicts: Wrong Answer

Accepted
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):
# encoding:utf-8

import sys
sys.setrecursionlimit(100000)

def main():
	n = int(input())
	vers = [list(map(int, input().split())) for _ in range(n - 1)]
	q, k = list(map(int, input().split()))
	queries = [list(map(int, input().split())) for _ in range(q)]

	n = 10 ** 5
	vers = [[i + 1, i + 2, 10 ** 9] for i in range(n - 1)]
	print(vers)

	new_vers = mapping(n, vers)
	dist = calcMinDist(n, new_vers, k, queries)
	print(dist)
	calcQueries(dist, queries, k)
	
def mapping(n, vers):
	new_vers = {i :[] for i in range(n)}
	for ver in vers:
		new_vers[ver[0] - 1].append((ver[1], ver[2]))
		new_vers[ver[1] - 1].append((ver[0], ver[2]))
	return new_vers

def calcMinDist(n, new_vers, k, queries):
	dist = [- 1 for _ in range(n)]
	flag = [False for _ in range(n)]
	dist[k - 1] = 0
	flag[k - 1] = True
	dfs(new_vers, dist, flag, k)
	return dist

def dfs(new_vers, dist, flag, frm):
	flag[frm - 1] = True
	vs = new_vers[frm - 1]
	for v in vs:
		if flag[v[0] - 1] == False:
			dist[v[0] - 1] = dist[frm - 1] + v[1]
			new_ver, dist, flag, _ = dfs(new_vers, dist, flag, v[0])

	return [new_vers, dist, flag, frm]

def calcQuery(dist, query, k):
	print(dist[query[0] - 1] + dist[query[1] - 1])

def calcQueries(dist, queries, k):
	for query in queries:
		calcQuery(dist, query, k)

if __name__ == '__main__':
	main()

# encoding:utf-8
import sys
 
def main():
	n = int(input())
	vers = [list(map(int, input().split())) for _ in range(n - 1)]
	q, k = list(map(int, input().split()))
	queries = [list(map(int, input().split())) for _ in range(q)]
 
	#n = 10 ** 5
	
 
	new_vers = mapping(n, vers)
	dist = calcMinDist(n, new_vers, k, queries)
	calcQueries(dist, queries, k)
	
def mapping(n, vers):
	new_vers = {i :[] for i in range(n)}
	for ver in vers:
		new_vers[ver[0] - 1].append((ver[1], ver[2]))
		new_vers[ver[1] - 1].append((ver[0], ver[2]))
	return new_vers
 
def calcMinDist(n, new_vers, k, queries):
	dist = [- 1 for _ in range(n)]
	flag = [False for _ in range(n)]
	dist[k - 1] = 0
	flag[k - 1] = True
	dfs(new_vers, dist, flag, k)
	return dist
 
def dfs(new_vers, dist, flag, frm):
	flag[frm - 1] = True
	vs = new_vers[frm - 1]
	for v in vs:
		if flag[v[0] - 1] == False:
			dist[v[0] - 1] = dist[frm - 1] + v[1]
			new_ver, dist, flag, _ = dfs(new_vers, dist, flag, v[0])
 
	return [new_vers, dist, flag, frm]
 
def calcQuery(dist, query, k):
	print(dist[query[0] - 1] + dist[query[1] - 1])
 
def calcQueries(dist, queries, k):
	for query in queries:
		calcQuery(dist, query, k)
 
if __name__ == '__main__':
	sys.setrecursionlimit(1000000)
	main()

Verdicts: Runtime Error

Accepted
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 numpy as np
from scipy.sparse.csgraph import floyd_warshall



n = int(input())
matrix = np.zeros((n, n))
for i in range(n-1):
    a, b, c = map(int, input().split())
    matrix[a-1][b-1] = c
    matrix[b-1][a-1] = c
min_span_matrix = floyd_warshall(matrix, directed=False,
                                 return_predecessors=False)
q, k = map(int, input().split())
for i in range(q):
    x, y = map(int, input().split())
    print(min_span_matrix[x-1][k-1] + min_span_matrix[k-1][y-1])


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


n = int(input())
query = [[] for i in range(n)]
for i in range(n-1):
    a, b, c = map(int, input().split())
    query[a-1].append((b-1, c))
    query[b-1].append((a-1, c))
q, k = map(int, input().split())
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 lis:
        if nx == per:
            continue
        if c != 0:
            stack.append((nx, cnt+c, now))
for i in range(q):
    x, y = map(int, input().split())
    print(dist[x-1] + dist[y-1])


Verdicts: Runtime Error

Accepted
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):
def BFS(K,edges,N):
  roots=[ [] for i in range(N)]
  for a,b,c in edges:
    roots[a-1]+=[(b-1,c)]
    roots[b-1]+=[(a-1,c)]
  dist=[-1]*N
  stack=[]
  stack.append(K)
  dist[K]=0
  while stack:
    label=stack.pop(-1)
    for i,c in edges[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        stack+=[i]
  return dist
 
N=int(input())
edges=[]
for i in range(N-1):
  edges+=[list(map(int,input().split()))]
Q,K=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(Q)]
distance=BFS(K-1,edges,N)
for i in range(Q):
  print(distance[xy[i][0]-1]+distance[xy[i][1]-1])

def BFS(K,edges,N):
  roots=[ [] for i in range(N)]
  for a,b,c in edges:
    roots[a-1]+=[(b-1,c)]
    roots[b-1]+=[(a-1,c)]
  dist=[-1]*N
  stack=[]
  stack.append(K)
  dist[K]=0
  while stack:
    label=stack.pop(-1)
    for i,c in roots[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        stack+=[i]
  return dist
 
N=int(input())
edges=[]
for i in range(N-1):
  edges+=[list(map(int,input().split()))]
Q,K=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(Q)]
distance=BFS(K-1,edges,N)
for i in range(Q):
  print(distance[xy[i][0]-1]+distance[xy[i][1]-1])

Verdicts: Runtime Error

Accepted
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):
from collections import defaultdict
import sys

sys.setrecursionlimit(1000000)
d=defaultdict(list)

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

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


dists=[None]*(N+1)
isused=[False]*(N+1)
dists[K]=0
isused[K]=True

def dfs(n):
    for i,j in d[n]:
        if isused[i]:continue
        isused[i]=True
        print(i,j)
        dists[i]=dists[n]+j
        dfs(i)

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

from collections import defaultdict
import sys

sys.setrecursionlimit(1000000)
d=defaultdict(list)

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

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


dists=[None]*(N+1)
isused=[False]*(N+1)
dists[K]=0
isused[K]=True

def dfs(n):
    for i,j in d[n]:
        if isused[i]:continue
        isused[i]=True
        dists[i]=dists[n]+j
        dfs(i)

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

Verdicts: Wrong Answer

Accepted
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):

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

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

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


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

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

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

Verdicts: Runtime Error

Accepted
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):

from collections import defaultdict,deque
import sys
finput=lambda: sys.stdin.readline().strip()

def main():
  n=int(finput())
  edges=[tuple(map(int,finput().split())) for _ in range(n-1)]
  q,k=map(int,finput().split())
  xy=[tuple(map(int,finput().split())) for _ in range(q)]
  ed=defaultdict(deque)
  wt=defaultdict(int)
  for e in edges:
    ed[e[0]].append(e[1])
    ed[e[1]].append(e[0])
    wt[(e[0],e[1])]=e[2]
    wt[(e[1],e[0])]=e[2]
  stack=deque([k])
  cv=stack[0]
  dist=defaultdict(int)
  while stack:
    while ed[cv]:
      if cv!=k:
        if ed[cv][-1]==stack[-1]:
          ed[cv].pop()
          if not ed[cv]:
            break
      stack.append(cv)
      cv=ed[cv].pop()
      dist[cv]=dist[stack[-1]]+wt[(stack[-1],cv)]
    cv=stack.pop()
  print(dist)
  for que in xy:
    print(dist[que[0]]+dist[que[1]])

if __name__=='__main__':
    main()


from collections import defaultdict,deque
import sys
finput=lambda: sys.stdin.readline().strip()

def main():
  n=int(finput())
  edges=[tuple(map(int,finput().split())) for _ in range(n-1)]
  q,k=map(int,finput().split())
  xy=[tuple(map(int,finput().split())) for _ in range(q)]
  ed=defaultdict(deque)
  wt=defaultdict(int)
  for e in edges:
    ed[e[0]].append(e[1])
    ed[e[1]].append(e[0])
    wt[(e[0],e[1])]=e[2]
    wt[(e[1],e[0])]=e[2]
  stack=deque([k])
  cv=stack[0]
  dist=defaultdict(int)
  while stack:
    while ed[cv]:
      if cv!=k:
        if ed[cv][-1]==stack[-1]:
          ed[cv].pop()
          if not ed[cv]:
            break
      stack.append(cv)
      cv=ed[cv].pop()
      dist[cv]=dist[stack[-1]]+wt[(stack[-1],cv)]
    cv=stack.pop()
  for que in xy:
    print(dist[que[0]]+dist[que[1]])

if __name__=='__main__':
    main()


Verdicts: Wrong Answer

Accepted
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 sys
from collections import deque
input = sys.stdin.readline
n = int(input())
edges = [[]for _ in range(n)]
for _ in range(n-1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append((c, b))
    edges[b].append((c, a))
INF = float('inf')


def bfs(init_v):
    dist = [INF]*n
    dist[init_v] = 0
    tasks = deque([(0, init_v)])
    while tasks:
        print(tasks)
        d, v = tasks.popleft()
        for d2, v2 in edges[v]:
            if dist[v2] <= dist[v]+d2:
                continue
            dist[v2] = dist[v]+d2
            tasks.append((dist[v2], v2))
    return dist


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

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n = int(input())
edges = [[]for _ in range(n)]
for _ in range(n-1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append((c, b))
    edges[b].append((c, a))
INF = float('inf')


def dfs(v, parent, distance):
    dist[v] = distance
    for d, v2 in edges[v]:
        if parent == v2:
            continue
        dfs(v2, v, distance+d)


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

Verdicts: Wrong Answer

Accepted
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):
N=int(input())
abc=[tuple(map(int,input().split())) for i in range(N-1)]
g=[set() for i in range(N)]
for a,b,c in abc:
  g[a-1].add((b-1,c))
  g[b-1].add((a-1,c))
memo=[0]*N
memo[K-1]=0
Q,K=map(int,input().split())
import collections
q=collections.deque([(K-1,0)])
while(q):
  x,w = q.popleft()
  for a,b in g[x]:
    if memo[a]==-1:
      memo[a]=w+b
      q.append((a,w+b))
  
for i in range(Q):
  x,y=map(int,input().split())
  print(memo[a-1]+memo[b-1])

N=int(input())
abc=[tuple(map(int,input().split())) for i in range(N-1)]
g=[set() for i in range(N)]
for a,b,c in abc:
  g[a-1].add((b-1,c))
  g[b-1].add((a-1,c))
memo=[-1]*N

Q,K=map(int,input().split())
import collections
q=collections.deque([(K-1,0)])
memo[K-1]=0
while(q):
  
  x,w = q.popleft()
  for a,b in g[x]:
    if memo[a]==-1:
      memo[a]=w+b
      q.append((a,w+b))
  
for i in range(Q):
  x,y=map(int,input().split())
  print(memo[x-1]+memo[y-1])


Verdicts: Runtime Error

Accepted
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):
n=int(input())-1

edges = {}
lens = {}
for _ in range(n):
    [a, b, c] = map(int, input().split())
    if a > b:
        a,b=b,a
    edges.setdefault(a, []).append(b)
    edges.setdefault(b, []).append(a)
    lens[(a,b)] = c

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

used = set()
dists = {}
def build(x, d=0):
    dists[x] = d
    for c in edges[x]:
        if c not in used:
            used.add(c)
            build(c, d + lens[(min(x,c), max(x,c))])

build(k)


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

n=int(input())-1

edges = {}
lens = {}
for _ in range(n):
    [a, b, c] = map(int, input().split())
    if a > b:
        a,b=b,a
    edges.setdefault(a, []).append(b)
    edges.setdefault(b, []).append(a)
    lens[(a,b)] = c

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

dists = {}
def build(x, d=0):
    ss = [(x, 0)]
    while ss:
        x, d = ss.pop()
        if x not in dists:
            dists[x] = d
            for c in edges.get(x, []):
                ss.append((c, d + lens[(min(x,c), max(x,c))]))

build(k)

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

Verdicts: Runtime Error

Accepted
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):
from heapq import heappush, heappop
from collections import defaultdict

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


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

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



INF = 1 << 60
dist = [INF] * (n + 1)
dist[k] = 0


q = [(0, k)]


while q:
    cost, curr = heappop(q)
    if cost > dist[curr]:
        continue
    for after, nc in graph[curr]:
        if cost + nc < dist[after]:
            dist[after] = cost + nc
            heappush(q, (cost + nc, after))

print("\n".join(map(str, (dist[x] + dist[y]
                          for x, y in (map(int, input().split()) for _ in range(q))))))

from heapq import heappush, heappop
from collections import defaultdict

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


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

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



INF = 1 << 60
dist = [INF] * (n + 1)
dist[k] = 0


que = [(0, k)]


while que:
    cost, curr = heappop(que)
    if cost > dist[curr]:
        continue
    for after, nc in graph[curr]:
        if cost + nc < dist[after]:
            dist[after] = cost + nc
            heappush(que, (cost + nc, after))
            
print(*([dist[x] + dist[y] for x, y in (map(int, input().split()) for _ in range(q))]), sep="\n")

Verdicts: Runtime Error

Accepted
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 sys
sys.setrecursionlimit(10**9)

input = sys.stdin.readline

N = int(input())
T = [[] for _ in range(N+1)]

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

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

dist = [None]*(N+1)

def dfs(now,d) :
    dist[now] = d
    for to,c in T[now] :
        if dist[to] is not None :
            continue
        dfs(to,d+c)

dfs(K,0)

ans = [0]*Q

for _ in range(Q) :
    u,v = map(int,input().split())
    ans[i] = dist[u]+dist[v]

print(*ans,sep="\n")


import sys
sys.setrecursionlimit(10**9)

input = sys.stdin.readline

N = int(input())

T = [[] for _ in range(N+1)]

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

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

dist = [None]*(N+1)

def dfs(now,d) :
    dist[now] = d
    for to,c in T[now] :
        if dist[to] is not None :
            continue
        dfs(to,d+c)

dfs(K,0)

ans = [0]*Q

for i in range(Q) :
    u,v = map(int,input().split())
    ans[i] = dist[u]+dist[v]

print(*ans,sep="\n")



Verdicts: Runtime Error

Accepted