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: Wrong Answer

Solution code:
#! /usr/bin/env python3
import sys

def main():
    L = []
    S = [x for x in sys.stdin]
    N = int(S.pop(0))
    D = [0] * (N+1)
    k = [1] * (N+1)
    sumk = 0
    for i in range(N-1):
        a, b, c = map(int, S[i].split())
        D[b] = (i, a)
        L.append(c)
    Q, K = map(int, S[N-1].split())
    tk = K
    kmemo = {}
    while D[tk]:
        a, tk = D[tk]
        k[a] = -1
        kmemo[a] = sumk
        sumk += L[a]
    memo = {}
    for i in range(N, N+Q):
        x, y = map(int, S[i].split())
        tx, ty = x, y
        if x not in memo:
            xsum = 0
            p = 0
            t = D[tx]
            while t:
                a, tx = t
                if k[a] < 0:
                    p = a
                    break
                xsum += L[a]
                t = D[tx]
            t = D[K]
            if p:
                xsum += kmemo[p]
            else:
                xsum += sumk
            memo[x] = xsum
        if y not in memo:
            ysum = 0
            p = 0
            t = D[ty]
            while t:
                a, ty = t
                if k[a] < 0:
                    p = a
                    break
                ysum += L[a]
                t = D[ty]
            t = D[K]
            if p:
                ysum += kmemo[p]
            else:
                ysum += sumk
            memo[y] = ysum
        sys.stdout.write(str(memo[x] + memo[y]) + '\n')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#! /usr/bin/env python3
import sys

def main():
    L = []
    S = [x for x in sys.stdin]
    N = int(S.pop(0))
    D = [0] * (N+1)
    k = [1] * (N+1)
    sumk = 0
    for i in range(N-1):
        a, b, c = map(int, S[i].split())
        D[b] = (i, a)
        L.append(c)
    Q, K = map(int, S[N-1].split())
    tk = K
    kmemo = {}
    while D[tk]:
        a, tk = D[tk]
        k[a] = -1
        sumk += L[a]
        kmemo[a] = sumk
    memo = {}
    for i in range(N, N+Q):
        x, y = map(int, S[i].split())
        tx, ty = x, y
        if x not in memo:
            xsum = 0
            p = 0
            t = D[tx]
            while t:
                a, tx = t
                if k[a] < 0:
                    p = a
                    break
                xsum += L[a]
                t = D[tx]
            t = D[K]
            if p:
                xsum += kmemo[p]
            else:
                xsum += sumk
            memo[x] = xsum
        if y not in memo:
            ysum = 0
            p = 0
            t = D[ty]
            while t:
                a, ty = t
                if k[a] < 0:
                    p = a
                    break
                ysum += L[a]
                t = D[ty]
            t = D[K]
            if p:
                ysum += kmemo[p]
            else:
                ysum += sumk
            memo[y] = ysum
        sys.stdout.write(str(memo[x] + memo[y]) + '\n')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

n = ni()
g = []
for i in range(n+1): g.append([])

for i in range(n-1):
    a, b, c = na()
    g[a].append((b,c))
    g[b].append((a,c))

q,k = na()

def dfs(cur, pre, g, par, dw, w):
    dw[cur] = w
    par[cur] = pre
    for e in g[cur]:
        if e[0] != pre:
            dfs(e[0], cur, g, par, dw, w + e[1])

par = [-1] * (n+2)
dw = [-1] * (n+2)
from asyncio import Queue
qs = Queue()
qs.put(k)
dw[k] = 0

while not qs.empty():
    cur = qs.get()
    for e in g[cur]:
        if e[0] != par[cur]:
            par[e[0]] = cur
            dw[e[0]] = dw[cur] + e[1]
            qs.put(e[0])


# dfs(k, -1, g, par, dw, 0)

for z in range(q):
    x, y = na()
    print(dw[x] + dw[y])

Submission status: Wrong Answer

Solution code:
#! /usr/bin/env python3
import sys

def main():
    L = []
    S = [x for x in sys.stdin]
    N = int(S.pop(0))
    D = [0] * (N+1)
    k = [1] * (N+1)
    sumk = 0
    for i in range(N-1):
        a, b, c = map(int, S[i].split())
        D[b] = (i, a)
        L.append(c)
    Q, K = map(int, S[N-1].split())
    tk = K
    while D[tk]:
        a, tk = D[tk]
        k[a] = -1
        sumk += L[a]
    memo = {}
    for i in range(N, N+Q):
        x, y = map(int, S[i].split())
        tx, ty = x, y
        if x not in memo:
            xsum = 0
            p = 0
            t = D[tx]
            while t:
                a, tx = t
                if k[a] < 0:
                    p = a
                    break
                xsum += L[a]
                t = D[tx]
            t = D[K]
            if p:
                while t:
                    a, tk = t
                    if a == p : break
                    xsum += L[a]
                    t = D[tk]
            else:
                xsum += sumk
            memo[x] = xsum
        if y not in memo:
            ysum = 0
            p = 0
            t = D[ty]
            while t:
                a, ty = t
                if k[a] < 0:
                    p = a
                    break
                ysum += L[a]
                t = D[ty]
            t = D[K]
            if p:
                while t:
                    a, tk = t
                    if a == p : break
                    ysum += L[a]
                    t = D[tk]
            else:
                ysum += sumk
            memo[y] = ysum
        sys.stdout.write(str(memo[x] + memo[y]) + '\n')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

def f(diu, n):
    r = []
    try:
        while n != 1:
            r = [diu[n][0]] + r
            n = diu[n][1]
    except:
        pass
    return r

memo = {}
def d(p, a, b, k):
    if k in memo : return memo[k]
    c = 0
    for i, j in zip(a, b):
        if i == j:
            c += 1
        else:
            break
    memo[k] = sum(p[x][2] for x in a[c:]) + sum(p[x][2] for x in b[c:])
    return memo[k]

def main():
    N = int(input())
    P = [tuple(map(int, input().split())) for x in range(N-1)]
    diu = {max(v[0], v[1]) : (i, min(v[0], v[1]))  for i, v in enumerate(P)}
    Q, K = map(int, input().split())
    k = f(diu, K)
    for i in range(Q):
        x, y = map(int, input().split())
        print(d(P, f(diu, x), k, (K, x)) + d(P, f(diu, y), k, (K, y)))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

def f(diu, n):
    r = []
    while n != 1:
        r = [diu[n][0]] + r
        n = diu[n][1]
    return r

def d(p, a, b):
    c = 0
    for i, j in zip(a, b):
        if i == j:
            c += 1
        else:
            break
    return sum(p[x][2] for x in a[c:]) + sum(p[x][2] for x in b[c:])

def main():
    N = int(input())
    P = [tuple(map(int, input().split())) for x in range(N-1)]
    diu = {v[1] : (i, v[0])  for i, v in enumerate(P)}
    M, K = map(int, input().split())
    XY = [tuple(map(int, input().split())) for x in range(M)]
    # k = f(diu, K)
    # for x, y in XY:
    #     print(d(P, f(diu, x), k) + d(P, f(diu, y), k))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())
edges = [[] for _ in range(N+1)]
for _ in range(N-1):
    ai, bi, ci = map(int, input().split())
    edges[ai].append((bi, ci))
    edges[bi].append((ai, ci))
Q, K = map(int, input().split())

distance = [-1]*(N+1)
# def add_weight(k, pre):
#     for v in edges[k]:
#         d, w = v
#         if d != pre:
#             distance[d] = w + distance[k]
#             add_weight(d, k)
# add_weight(K, -1)
que = deque()
que.append(K); distance[K] = 0
while len(que):
    a = que.popleft()
    for b, c in edges[a]:
        if distance[b] == -1:
            distance[b] = c + distance[a]
            que.append(b)

print(distance)

for _ in range(Q):
    s, e = map(int, input().split())
    print(distance[s] + distance[e])

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())
edges = [[] for _ in range(N+1)]
for _ in range(N-1):
    ai, bi, ci = map(int, input().split())
    edges[ai].append((bi, ci))
    edges[bi].append((ai, ci))
Q, K = map(int, input().split())

distance = [-1]*(N+1)
# def add_weight(k, pre):
#     for v in edges[k]:
#         d, w = v
#         if d != pre:
#             distance[d] = w + distance[k]
#             add_weight(d, k)
# add_weight(K, -1)
que = deque()
que.append(edges[K]); distance[K] = 0
while len(que):
    a = que.popleft()
    for b, c in a:
        if distance[b] == -1:
            distance[b] = c
            que.append(edges[b])

for _ in range(Q):
    s, e = map(int, input().split())
    print(distance[s] + distance[e])

Submission status: Wrong Answer

Solution code:
#!usr/bim/python
#! -*- coding: utf-8 -*-

import numpy as np

n = raw_input()
n = int(n)

tree = []
for i in range(n):
    tree.append([])

for i in range(n-1):
    abc = raw_input()
    abc = abc.split()
    abc = map(int, abc)
    tree[abc[0]-1].append([abc[1]-1,abc[2]])
    tree[abc[1]-1].append([abc[0]-1,abc[2]])


qk = raw_input()
qk = qk.split()
q,k = map(int,qk)

question = []
for i in range(q):
    xy = raw_input()
    xy = xy.split()
    xy = map(int,xy)
    question.append(xy)

print tree

distance = []
for i in range(n):
    distance.append(-1)

distance[k-1] = 0

while 1:
    status = 0
    for i in range(n):
        if distance[i] == -1:
            status = 1
        else:
            for j in tree[i]:
                if distance[j[0]] == -1:
                    distance[j[0]] = distance[i] + j[1]
    print distance
    if status == 0:
        break

for line in question:
    print distance[line[0]-1] + distance[line[1]-1]

Submission status: Wrong Answer

Solution code:
N = int(input())
g = {}
for i in range(1, N+1):
    g[i] = []

cache = {}
def dfs(g,start,end):
    if cache.get((start,end),None) != None:
        return cache[(start,end)]
    stack = [(start, [start], 0)]
    while stack:
        (v, path, length) = stack.pop()
        for next,l in g[v]:
            if next in path: continue
            if next == end:
                cache[(start,end)] = length + 1
                return cache[(start,end)]
            else:
                stack.append((next, path + [next], length + l))

for i in range(N-1):
    a, b, c = map(int,input().split())
    g[a].append((b,c))
    if (a,c) not in g[b]:
        g[b].append((a,c))
Q, K = map(int,input().split())

for q in range(Q):
    x, y = map(int,input().split())
    print(dfs(g,x,K) + dfs(g,K,y))

Submission status: Wrong Answer

Solution code:
N = int(input())
g = {}
for i in range(1, N+1):
    g[i] = []

cache = {}
def dfs(g,start,end):
    if cache.get((start,end),None) != None:
        return cache[(start,end)]
    stack = [(start, [start], 0)]
    while stack:
        (v, path, length) = stack.pop()
        for next,l in g[v]:
            if next in path: continue
            if next == end:
                cache[(start,end)] = length + 1
                return cache[(start,end)]
            else:
                stack.append((next, path + [next], length + l))

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

for q in range(Q):
    x, y = map(int,input().split())
    print(dfs(g,x,K) + dfs(g,K,y))

Submission status: Wrong Answer

Solution code:
a=[]
b=[]
c=[]

def connect(N,v):
    vs = []
    indices = []
    ws = []
    n = a.count(v)
    for i in range(n):
        if i == 0:
            indices.append(a.index(v))
        else:
            indices.append(a.index(v,indices[i-1]+1))
        ws.append(c[indices[i]])
        vs.append(b[indices[i]])
    m = b.count(v)
    for i in range(m):
        if i == 0:
            indices.append(b.index(v))
        else:
            indices.append(b.index(v,indices[i-1]+1))
        ws.append(c[indices[i]])
        vs.append(a[indices[i]])
    return (vs,indices,ws)

def minpath(N,k,cheat_pre,vertex,ind,w,univk):
  cheat_pre[vertex-1] = cheat_pre[k-1]+w
  vs,inds,ws = connect(N,vertex)
  for i in range(len(vs)):
      if cheat_pre[vs[i]-1] == 0 and vs[i] != univk:
        cheat_pre = minpath(N,vertex,cheat_pre,vs[i],inds[i],ws[i],univk)
  return cheat_pre

N=input()
for i in range(N-1):
  d,e,f = map(int, raw_input().split())
  a.append(d)
  b.append(e)
  c.append(f)
q,k = map(int, raw_input().split())
vs,inds,ws = connect(N,k)
cheat = [0 for i in range(N)]
for i in range(len(vs)):
    cheat = minpath(N,k,cheat,vs[i],inds[i],ws[i],k)
for i in range(q):
  x,y = map(int, raw_input().split())
  print (cheat[x-1] + cheat[y-1])

Submission status: Wrong Answer

Solution code:
def connect(N,a,b,c,v):
    vs = []
    indices = []
    ws = []
    n = a.count(v)
    for i in range(n):
        if i == 0:
            indices.append(a.index(v))
        else:
            indices.append(a.index(v,indices[i-1]+1))
        ws.append(c[indices[i]])
        vs.append(b[indices[i]])
    m = b.count(v)
    for i in range(m):
        if i == 0:
            indices.append(b.index(v))
        else:
            indices.append(b.index(v,indices[i-1]+1))
        ws.append(c[indices[i]])
        vs.append(a[indices[i]])
    return (vs,indices,ws)

def minpath(N,a,b,c,k,cheat_pre,vertex,ind,w,univk):
  cheat_pre[vertex-1] = cheat_pre[k-1]+w
  vs,inds,ws = connect(N,a,b,c,vertex)
  for i in range(len(vs)):
      if cheat_pre[vs[i]-1] == 0 and vs[i] != univk:
        cheat_pre = minpath(N,a,b,c,vertex,cheat_pre,vs[i],inds[i],ws[i],univk)
  return cheat_pre

N=input()
a=[]
b=[]
c=[]
for i in range(N-1):
  d,e,f = map(int, raw_input().split())
  a.append(d)
  b.append(e)
  c.append(f)
q,k = map(int, raw_input().split())
vs,inds,ws = connect(N,a,b,c,k)
cheat = [0 for i in range(N)]
for i in range(len(vs)):
    cheat = minpath(N,a,b,c,k,cheat,vs[i],inds[i],ws[i],k)
for i in range(q):
  x,y = map(int, raw_input().split())
  print (cheat[x-1] + cheat[y-1])

Submission status: Wrong Answer

Solution code:
import heapq
import copy
inf =10**10+7
N = int(input())
A = [ [inf for i in range(N)] for j in range(N)]
for n in range(N-1):
  a,b,c=map(int,input().split())
  A[a-1][b-1] = c
  A[b-1][a-1] = c
 
Q,K = map(int,input().split())
 
def Tree_search(A,start):
  num = len(A)
  dist = [inf for i in range(N)] 
  prev = [inf for i in range(N)] 
  
  dist[start] = 0
  
  
  def check(dist,prev,start):
    length = {}
  
    q = []
    heapq.heappush(q,(0,start))
    while len(q) != 0:
      c,src = heapq.heappop(q)
      if dist[src] < c:
        continue
      for dst in range(num):
        check = A[src][dst]
        if check != inf and dist[dst]>dist[src] + check:
          dist[dst]=dist[src] + check
          heapq.heappush(q,(dist[dst],dst))
          prev[dst] = src
    
    for n in range(N):
      length_min=0
      tmp_pos = copy.copy(n)
      while prev[tmp_pos] != inf:
        length_min += A[tmp_pos][prev[tmp_pos]]
        tmp_pos = prev[tmp_pos]
      length[n] =length_min
    
    return length
    
  
  return check(dist,prev,start)

Length = Tree_search(A,K-1) 

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

Submission status: Wrong Answer

Solution code:
import heapq
inf =10**10+7
N = int(input())
A = [ [inf for i in range(N)] for j in range(N)]
for n in range(N-1):
  a,b,c=map(int,input().split())
  A[a-1][b-1] = c
  A[b-1][a-1] = c
 
Q,K = map(int,input().split())
 
def Tree_search(A,start,center,goal):
  num = len(A)
  dist1 = [inf for i in range(N)] 
  dist2 = [inf for i in range(N)] 
  prev1 = [inf for i in range(N)] 
  prev2 = [inf for i in range(N)] 
    
  dist1[start] = 0
  dist2[center] = 0
  
  def check(dist,prev,start,goal):
    q = []
    heapq.heappush(q,(0,start))
    while len(q) != 0:
      c,src = heapq.heappop(q)
      if dist[src] < c:
        continue
      for dst in range(num):
        check = A[src][dst]
        if check != inf and dist[dst]>dist[src] + check:
          dist[dst]=dist[src] + check
          heapq.heappush(q,(dist[dst],dst))
          prev[dst] = src
    length_min=0
    while prev[goal] != inf:
      length_min += A[goal][prev[goal]]
      goal = prev[goal]
    return length_min
  
  return check(dist1,prev1,start,center)+check(dist2,prev2,center,goal)
 
for q in range(Q):
  x,y = map(int,input().split())
  print(Tree_search(A,x-1,K-1,y-1))

Submission status: Wrong Answer

Solution code:
import heapq
inf =10**10+7
N = int(input())
A = [ [inf for i in range(N)] for j in range(N)]
for n in range(N-1):
  a,b,c=map(int,input().split())
  A[a-1][b-1] = c
  A[b-1][a-1] = c

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

def Tree_search(A,start,goal):
  num = len(A)
  dist = [inf for i in range(N)] 
  prev = [inf for i in range(N)] 
    
  dist[start] = 0
  q = []
  heapq.heappush(q,(0,start))
  
  while len(q) != 0:
    c,src = heapq.heappop(q)
    if dist[src] < c:
      continue
    for dst in range(num):
      check = A[src][dst]
      if check != inf and dist[dst]>dist[src] + check:
        dist[dst]=dist[src] + check
        heapq.heappush(q,(dist[dst],dst))
        prev[dst] = src
  
  length_min=0
  while prev[goal] != inf:
    length_min += A[goal][prev[goal]]
    goal = prev[goal]
  return length_min

for q in range(Q):
  x,y = map(int,input().split())
  print(Tree_search(A,x-1,K-1) + Tree_search(A,K-1,y-1))

Submission status: Wrong Answer

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

import heapq


INF = 10 ** 8


def dijkstra(num_vertices, adj_list, source=0):
    dist = [INF for _ in range(num_vertices)]
    dist[source] = 0
    pq = [(dist[u], u) for u in range(num_vertices)]
    heapq.heapify(pq)
    while pq:
        _, u = heapq.heappop(pq)
        for v, cost in adj_list[u]:
            new_length = dist[u] + cost
            if new_length < dist[v]:
                dist[v] = new_length
                heapq.heappush(pq, (new_length, v))
    return dist


def main():
    n = int(input())
    adj_list = [set() for _ in range(n)]
    for _ in range(n - 1):
        a, b, c = (int(z) for z in input().split())
        a -= 1
        b -= 1
        adj_list[a].add((b, c))
        adj_list[b].add((a, c))
    q, k = (int(z) for z in input().split())
    k -= 1
    dist = dijkstra(n, adj_list, k)
    for _ in range(q):
        x, y = (int(z) - 1 for z in input().split())
        res = dist[x] + dist[y]
        print(res)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
f = [[] for i in range(N)]
for i in range(N-1):
    a,b,c = map(int,input().split())
    f[a-1].append([b-1,c])
    f[b-1].append([a-1,c])
from collections import deque
d = deque()
s = [-1]*N
Q,K = map(int,input().split())
for i in range(N):
    t = [-1]*N
    d.append(i)
    t[i] = 0
    if i == K-1:
        Flag = False
        z = d.clear()
    else:
        Flag = True
    while Flag:
        z = d.popleft()
        for j,c in f[z]:
            if t[j] == -1:
                t[j] = c+t[z]
                d.append(j)
            if j == K-1:
                Flag = False
                d.clear()
                break
    s[i] = t[K-1]
for i in range(Q):
    x,y = map(int,input().split())
    print(s[x-1]+s[y-1])

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy,bisect
from operator import itemgetter

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
nf = lambda: float(ns())
na = lambda: list(map(int, stdin.readline().split()))
nb = lambda: list(map(float, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces


def bellman_ford(s, n):
    d = [inf]*n # 各頂点への最小コスト
    d[s] = 0 # 自身への距離は0
    for i in range(n):
        update = False # 更新が行われたか
        for x, y, z in g:
            if d[y] > d[x] + z:
                d[y] = d[x] + z
                update = True
        if not update:
            break
        # 負閉路が存在
        if i == n - 1:
            return -1
    return d

N = ni()
g = []
for _ in range(N-1):
    a, b, c = na()
    g.append([a-1, b-1, c])
    g.append([b-1, a-1, c])

Q, K = na()
ans = []
d = bellman_ford(K-1, N)
for i in range(Q):
    x, y = na()
    x -= 1
    y -= 1
    ans.append(d[x] + d[y])
for i in range(Q):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
INF = float('inf')
Map = [[INF]*N for _ in range(N)]
for _ in range(N-1):
  a,b,c = map(int,input().split())
  Map[a-1][b-1] = c
  Map[b-1][a-1] = c
for k in range(N):
  for i in range(N):
    for j in range(N):
      Map[i][j] = min(Map[i][j],Map[i][k]+Map[k][j])
Q,K = map(int,input().split())
for _ in range(Q):
  x,y = map(int,input().split())
  ans = Map[x-1][K-1] + Map[K-1][y-1]
  print(ans)

Submission status: Time Limit Exceeded

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

visited=[-1 for i in range(N)]
Q,K=map(int,input().split())
visited[K-1]=0
q=[K-1]
while q:
  u=q.pop(0)
  for v,d in tree[u]:
    if visited[v]==-1:
      visited[v]=visited[u]+d
      q.append(v)
    
for i in range(Q):
  x,y=map(int,input().split())
  print(visited[x-1]+visited[y-1])

Submission status: Time Limit Exceeded

Solution code:
import heapq

INF = float('inf')

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

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

Q, K = map(int, input().split())
query = [list(map(lambda x:int(x) - 1, input().split())) for _ in range(Q)]


def dijkstra(s, e):
    hq = [(0, s)]
    heapq.heapify(hq) # リストを優先度付きキューに変換
    cost = [INF] * N # 行ったことのないところはinf
    cost[s] = 0 # 開始地点は0
    
    while hq:
        c, v = heapq.heappop(hq)
        if c > cost[v]: # コストが現在のコストよりも高ければスルー
            continue
        for d, u in to[v]:
            tmp = d + cost[v]
            if tmp < cost[u]:
                cost[u] = tmp
                heapq.heappush(hq, (tmp, u))
    return cost[e]


def main():
    min_path = [dijkstra(i, K - 1) for i in range(N)]
    for x, y in query:
        print(min_path[x] + min_path[y])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq

INF = float('inf')

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

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

Q, K = map(int, input().split())
query = [list(map(lambda x:int(x) - 1, input().split())) for _ in range(Q)]


def dijkstra(s, e):
    hq = [(0, s)]
    heapq.heapify(hq) # リストを優先度付きキューに変換
    cost = [INF] * N # 行ったことのないところはinf
    cost[s] = 0 # 開始地点は0
    
    while hq:
        c, v = heapq.heappop(hq)
        if c > cost[v]: # コストが現在のコストよりも高ければスルー
            continue
        for d, u in to[v]:
            tmp = d + cost[v]
            if tmp < cost[u]:
                cost[u] = tmp
                heapq.heappush(hq, (tmp, u))
    return cost[e]


def main():
    for x, y in query:
        print(dijkstra(x, K - 1) + dijkstra(y, K - 1))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
# sys.setrecursionlimit(100000)
from collections import defaultdict


def warshall_floyd(graph: dict, N: int):
    """ graph:
    {node:{node:cost,node:cost,...},
     node:{node:cost,node:cost,...},...}
    """
    INF = float("inf")
    dp = [[INF] * N for _ in range(N)]
    for i in range(N):
        dp[i][i] = 0

    # Step 1: fill dp
    for v1, edges in graph.items():
        for v2, cost in edges.items():
            dp[v1][v2] = cost

    # search
    for k in range(N):  # 中継点
        for i in range(N):  # 始点
            for j in range(N):  # 終点
                dp[i][j] = min(dp[i][k] + dp[k][j], dp[i][j])

    return dp


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    n = input_int()
    graph = defaultdict(dict)
    for _ in range(n - 1):
        a, b, c = input_int_list()
        graph[a][b] = c
        graph[b][a] = c
    dp = warshall_floyd(graph, n + 1)
    q, k = input_int_list()
    ans = []
    for _ in range(q):
        x, y = input_int_list()
        ans.append(dp[x][k] + dp[k][y])

    for i in ans:
        print(i)

    return


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from scipy.sparse.csgraph import dijkstra
    n = int(input())
    G = [[float('inf') for i in range(n)] for i in range(n)]
    for _ in range(n-1):
        a,b,c = map(int,input().split())
        G[a-1][b-1] = G[b-1][a-1] = c
    q,k = map(int,input().split())
    d = dijkstra(G)[k-1]
    for _ in range(q):
        x,y = map(int,input().split())
        print(int(d[x-1]+d[y-1]))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def dijkstra(g,n,s):
    '''
    input
        g: n x n　list
        n: int
        s: start index
    '''
    d = [float('inf')]*n
    U = [i for i in range(n)]
    d[s] = 0
    while len(U)>0:
        w = U[0]
        for u in U:
            if d[u]<d[w]:
                w = u
        U.pop(U.index(w))
        for v in U:
            d[v] = min(d[v],d[w]+g[w][v])
    return d

def main():
    n = int(input())
    G = [[float('inf') for i in range(n)] for i in range(n)]
    for _ in range(n-1):
        a,b,c = map(int,input().split())
        G[a-1][b-1] = G[b-1][a-1] = c
    q,k = map(int,input().split())
    d = dijkstra(G, n, k-1)
    for _ in range(q):
        x,y = map(int,input().split())
        print(d[x-1]+d[y-1])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
 
def bellman_ford(s):
	d = [float('inf')]*n # 各頂点への最小コスト
	d[s] = 0 # 自身への距離は0
	for i in range(n):
		update = False # 更新が行われたか
		for x, y, z in g:
			if d[y] > d[x] + z:
				d[y] = d[x] + z
				update = True
		if not update:
 			break
		# 負閉路が存在
		if i == n-1:
			return -1
	return d

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

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

Submission status: Time Limit Exceeded

Solution code:
import heapq

def dijkstra(s):
	hq = [(0, s)]
	heapq.heapify(hq) # リストを優先度付きキューに変換
	cost = [float('inf')] * n # 行ったことのないところはinf
	cost[s] = 0 # 開始地点は0
	while hq:
		c, v = heapq.heappop(hq)
		if c > cost[v]: # コストが現在のコストよりも高ければスルー
			continue
		for d, u in e[v]:
			tmp = d + cost[v]
			if tmp < cost[u]:
				cost[u] = tmp
				heapq.heappush(hq, (tmp, u))
	return cost

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
 
def bellman_ford(s):
	d = [float('inf')]*n # 各頂点への最小コスト
	d[s] = 0 # 自身への距離は0
	for i in range(n):
		update = False # 更新が行われたか
		for x, y, z in g:
			if d[y] > d[x] + z:
				d[y] = d[x] + z
				update = True
		if not update:
 			break
		# 負閉路が存在
		if i == n-1:
			return -1
	return d

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
points = [list(map(int,input().split())) for _ in range(N-1)]
Q, K = map(int,input().split())
Query = [list(map(int,input().split())) for _ in range(Q)]

tree = [[0]*N for _ in range(N)]
for i in range(N-1):
    a = points[i][0] - 1
    b = points[i][1] - 1
    tree[a][b] = points[i][2]
    tree[b][a] = points[i][2]
def  bfs(u,q):
    queue = deque([u])
    cost = [None]*N
    cost[u] = 0
    while queue:
        v = queue.popleft()
        for i in range(N):
            if tree[v][i] != 0 and cost[i] == None:
                cost[i] =cost[v] + tree[v][i]
                queue.append(i)
    return cost[q]
answer = [0]*Q
for i in range(Q):
    answer[i] = bfs(Query[i][0]-1,K-1) + bfs(K-1,Query[i][1]-1)

for distance in answer:
    print(distance)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
points = [list(map(int,input().split())) for _ in range(N-1)]
Q, K = map(int,input().split())
Query = [list(map(int,input().split())) for _ in range(Q)]

tree = [[0]*N for _ in range(N)]
for i in range(N-1):
    a = points[i][0] - 1
    b = points[i][1] - 1
    tree[a][b] = points[i][2]
    tree[b][a] = points[i][2]
def  bfs(u,q):
    queue = deque([u])
    cost = [None]*N
    cost[u] = 0
    while queue:
        v = queue.popleft()
        for i in range(N):
            if tree[v][i] != 0 and cost[i] == None:
                cost[i] =cost[v] + tree[v][i]
                queue.append(i)
    return cost[q]
answer = [0]*Q
for i in range(Q):
    answer[i] = bfs(Query[i][0]-1,K-1) + bfs(K-1,Query[i][1]-1)

for distance in answer:
    print(distance)