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


def main():
    n = int(input())
    tree = AdjacentListGraph([Vertex() for _ in range(n)])
    for _ in range(n - 1):
        a, b, c = map(int, input().split())
        tree.add_edge(a - 1, b - 1, c)
        tree.add_edge(b - 1, a - 1, c)
    q, k = map(int, input().split())
    distances = distances_from(tree, k - 1)
    # print(distances)
    answers = []
    for _ in range(q):
        x, y = map(int, input().split())
        answers.append(distances[x - 1] + distances[y - 1])
    print("\n".join(map(str, answers)))


def distances_from(
    graph: "Graph", from_: int, break_if=lambda node: False
) -> "List[int]":
    distances = [None for _ in range(graph.size)]
    distances[from_] = 0
    queue = deque([from_])
    while queue:
        node = queue.popleft()
        if break_if(node):
            break
        curDist = distances[node]
        for edge in graph.edges_from(node):
            if distances[edge.to] is not None:
                continue
            delta = edge.weight if edge.weight else 0
            distances[edge.to] = curDist + delta
            queue.append(edge.to)
    return distances


class Vertex:
    __slots__ = ("data", "edges")

    def __init__(self, data=None):
        self.data = data
        self.edges = []

    def add_edge(self, to, weight=None) -> bool:
        for edge in self.edges:
            if edge.to == to:
                return False
        self.edges.append(Edge(to, weight))
        return True

    def remove_edge(self, to: int) -> bool:
        for i, edge in enumerate(self.edges):
            if edge.to == to:
                del self.edges[i]
                return True
        return False


class Edge:
    __slots__ = ("to", "weight")

    def __init__(self, to, weight=None):
        self.to = to
        self.weight = weight


class AdjacentListGraph:
    def __init__(self, vertices):
        self.vertices = vertices
        self.size = len(vertices)

    def get_weight(self, from_: int, to: int):
        for edge in self.vertices[from_].edges:
            if edge.to == to:
                return edge.weight
        return None

    def edges_from(self, from_: int):
        return self.vertices[from_].edges

    def add_edge(self, from_: int, to: int, weight=None) -> bool:
        return self.vertices[from_].add_edge(to, weight)

    def remove_edge(self, from_: int, to: int) -> bool:
        return self.vertices[from_].remove_edge(to)

    def is_adjacent(self, from_: int, to: int) -> bool:
        return to in {edge.to for edge in self.edges_from(from_)}


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000) 
N=int(input())
Branch=[[] for i in range(N)]
for i in range(N-1):
  a,b,c=map(int,input().split())
  Branch[a-1].append([b-1,c])
  Branch[b-1].append([a-1,c])
Q,K=map(int,input().split())
DistK=[float("Inf") for i in range(N)]
flag = [0 for i in range(N)]

def dfs(s,dist):
  DistK[s]=dist
  flag[s]=1
  
  for i in range(len(Branch[s])):
    if flag[Branch[s][i][0]]==0:
      dfs(Branch[s][i][0],dist+Branch[s][i][1])
      
  return 1
dfs(K-1,0)
for i in range(Q):
  x,y = map(int,input().split())
  print(DistK[x-1]+DistK[y-1])

Submission status: Time Limit Exceeded

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

n = int(input())

from collections import defaultdict
d = defaultdict(list)

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

global dist
dist = [-1 for _ in range(n)]
def dfs(l, pos):
    dist[pos] = l
    for to, c in d[pos]:
        if dist[to] == -1:
            dfs(l+c,to)

dfs(0, k-1)

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

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
import sys
import copy
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def main():
    n=int(input())
    graph = [[] for _ in range(n)]
    for _ in range(n-1):
        a,b,w=map(int,input().split())
        a-=1
        b-=1
        graph[a].append((b,w))
        graph[b].append((a,w))
    graph = tuple(graph)
    q,k = map(int,input().split())
    pre = []
    que = deque()
    for e in range(n):
        dis = [-1 for _ in range(n)]
        dis[e]=0
        if e == k-1:
            pre.append(0)
        else:
            que.append(e)
        while que:
            i = que.pop()
            for j in range(len(graph[i])):
                go = graph[i][j][0]
                d = graph[i][j][1]
                if dis[go]!=-1:
                    continue
                dis[go] = dis[i] + d
                if k-1 == go:
                    pre.append(dis[go])
                    que=deque()
                    break
                que.append(go)
    pre = tuple(pre)
    for _ in range(q):
        x,y = map(int,input().split())
        print( pre[x-1] + pre[y-1] ) 

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
import sys
import copy
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def main():
    n=int(input())
    graph = [[] for _ in range(n)]
    for _ in range(n-1):
        a,b,w=map(int,input().split())
        a-=1
        b-=1
        graph[a].append((b,w))
        graph[b].append((a,w))
    graph = tuple(graph)
    q,k = map(int,input().split())
    pre1 = []
    pre2 = []
    que = deque()
    for e in range(n):
        dis = [-1 for _ in range(n)]
        dis[e]=0
        if e == k-1:
            pre1.append(0)
        else:
            que.append(e)
        while que:
            tank = deque()
            while que:
                i = que.pop()
                for j in range(len(graph[i])):
                    go = graph[i][j][0]
                    d = graph[i][j][1]
                    if dis[go]!=-1:
                        continue
                    dis[go] = dis[i] + d
                    if k-1 == go:
                        pre1.append(dis[go])
                        tank=deque()
                        que=deque()
                        break
                    tank.append(go)
            que = tank
    que = deque()
    que.append(k-1)
    dis = [-1 for _ in range(n)]
    dis[k-1]=0
    while que:
        tank = []
        while que:
            i = que.pop()
            for j in range(len(graph[i])):
                go = graph[i][j][0]
                d = graph[i][j][1]
                if dis[go]!=-1:
                    continue
                dis[go] = dis[i] + d
                tank.append(go)
        que = tank
    pre2 = dis

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
import sys
import copy
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def main():
    n=int(input())
    graph = [[] for _ in range(n)]
    for _ in range(n-1):
        a,b,w=map(int,input().split())
        a-=1
        b-=1
        graph[a].append((b,w))
        graph[b].append((a,w))
    graph = tuple(graph)
    q,k = map(int,input().split())
    pre1 = []
    pre2 = []
    que = deque()
    for e in range(n):
        que.append(e)
        dis = [0 for _ in range(n)]
        did = [False for _ in range(n)]
        did[e] = True
        if e == k-1:
            pre1.append(0)
        while que:
            tank = deque()
            while que:
                i = que.pop()
                for j in range(len(graph[i])):
                    go = graph[i][j][0]
                    d = graph[i][j][1]
                    if did[go]:
                        continue
                    dis[go] = dis[i] + d
                    if k-1 == go:
                        pre1.append(dis[go])
                        tank=deque()
                        que=deque()
                        break
                    tank.append(go)
                    did[go] = True
            que = tank
    que = deque()
    que.append(k-1)
    dis = [0 for _ in range(n)]
    did = [False for _ in range(n)]
    did[k-1] = True
    while que:
        tank = []
        while que:
            i = que.pop()
            for j in range(len(graph[i])):
                go = graph[i][j][0]
                d = graph[i][j][1]
                if did[go]:
                    continue
                dis[go] = dis[i] + d
                tank.append(go)
                did[go] = True
        que = tank
    pre2 = dis

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
import sys
import copy
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def main():
    n=int(input())
    graph = [[] for _ in range(n)]
    for _ in range(n-1):
        a,b,w=map(int,input().split())
        a-=1
        b-=1
        graph[a].append((b,w))
        graph[b].append((a,w))
    graph = tuple(graph)
    q,k = map(int,input().split())
    pre1 = []
    pre2 = []
    for e in range(n):
        que = [e]
        dis = [0 for _ in range(n)]
        did = [False for _ in range(n)]
        did[e] = True
        if e == k-1:
            pre1.append(0)
        while que:
            tank = []
            for i in que:
                for j in range(len(graph[i])):
                    go = graph[i][j][0]
                    d = graph[i][j][1]
                    if did[go]:
                        continue
                    dis[go] = dis[i] + d
                    if k-1 == go:
                        pre1.append(dis[go])
                        tank=[]
                        que=[]
                        break
                    tank.append(go)
                    did[go] = True
            que = tank
        
    que = [k-1]
    dis = [0 for _ in range(n)]
    did = [False for _ in range(n)]
    did[k-1] = True
    while que:
        tank = []
        for i in que:
            for j in range(len(graph[i])):
                go = graph[i][j][0]
                d = graph[i][j][1]
                if did[go]:
                    continue
                dis[go] = dis[i] + d
                tank.append(go)
                did[go] = True
        que = tank
    pre2 = dis
 
    pre1 = tuple(pre1)
    pre2 = tuple(pre2)
    for _ in range(q):
        x,y = map(int,input().split())
        print( pre1[x-1] + pre2[y-1] ) 

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
import sys
import copy
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
    
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])
def graphm():
    n=inp()
    g=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b,w=inpm()
        a-=1
        b-=1
        g[a].append((b,w))
        g[b].append((a,w))
    return n,g

def dfs(start,goal,n,g):
    que = [start-1]
    dis = [0 for _ in range(n)]
    did = [False for _ in range(n)]
    did[start-1] = True
    if start == goal:
        return 0
    while que:
        tank = []
        for i in que:
            for j in range(len(g[i])):
                go = g[i][j][0]
                d = g[i][j][1]
                if did[go]:
                    continue
                dis[go] = dis[i] + d
                if goal-1 == go:
                    return dis[go]
                tank.append(go)
                did[go] = True
        que = tank
 
def main():
    n,graph = graphm()
    q,k = inpm()
    pre1 = []
    pre2 = []
    for i in range(n):
        pre1.append(dfs(i+1,k,n,graph))
        pre2.append(dfs(k,i+1,n,graph))
    for _ in range(q):
        x,y = inpm()
        print( pre1[x-1] + pre2[y-1] ) 

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
import sys
import copy
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
    
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])
def graphm():
    n=inp()
    g=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b,w=inpm()
        a-=1
        b-=1
        g[a].append((b,w))
        g[b].append((a,w))
    return n,g
def dijkstra(s,to,n,g): # sからの最短距離 頂点数n
    s -= 1
    que = []
    d = [10**15 for _ in range(n)]
    d[s] = 0
    heappush( que,(0,s) )
    while len(que)>0:
        p =  heappop(que)
        v = p[1]
        if d[v] < p[0]:
            if p[1]==to-1:
                break
            continue
        for i in range(len(g[v])):
            edge = g[v][i]
            if d[edge[0]] > d[v] + edge[1]:
                d[edge[0]] = d[v] + edge[1]
                heappush( que,(d[edge[0]] , edge[0]) )
    return d[to-1]
 
def dijkstra1(s,n,g): # sからの最短距離 頂点数n
    s -= 1
    que = []
    d = [10**15 for _ in range(n)]
    d[s] = 0
    heappush( que,(0,s) )
    while len(que)>0:
        p =  heappop(que)
        v = p[1]
        if d[v] < p[0]:
            continue
        for i in range(len(g[v])):
            edge = g[v][i]
            if d[edge[0]] > d[v] + edge[1]:
                d[edge[0]] = d[v] + edge[1]
                heappush( que,(d[edge[0]] , edge[0]) )
    return d
 
def main():
    n,graph = graphm()
    q,k = inpm()
    pre2 = dijkstra1(k,n,graph)
    pre1=[]
    for i in range(n):
        pre1.append(dijkstra(i+1,k,n,graph))
    for _ in range(q):
        x,y = inpm()
        print( pre1[x-1] + pre2[y-1] ) 

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# disjoint setかと思いきやDFS
# したらTLEになったので根本的にやり方が間違ってるということ
# よくよく考えたらdfsなのでそこにたどり着いたときが最短距離だわ ムダに探索してた


import sys

sys.setrecursionlimit(10000000)

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

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

q, k = map(int, input().split())
k = k - 1
# kからスタートしてぜんぶたどる
ans_list = [0 for _ in range(n)]


def dfs(node, weight):
    for data in graph[node]:
        if not used[data[0]]:
            used[data[0]] = True
            dfs(data[0], weight + data[1])
    ans_list[node] = weight


used = [False for _ in range(n)]
used[k] = True
dfs(k, 0)

for _ in range(q):
    a, b = map(lambda x: int(x) - 1, input().split())
    print(ans_list[a] + ans_list[b])

Submission status: Time Limit Exceeded

Solution code:
# disjoint setかと思いきやDFS
# したらTLEになったので根本的にやり方が間違ってるということ
# よくよく考えたらdfsなのでそこにたどり着いたときが最短距離だわ ムダに探索してた


import sys

sys.setrecursionlimit(10000000)

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

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

q, k = map(int, input().split())
k = k - 1
# kからスタートしてぜんぶたどる
ans_list = [0 for _ in range(n)]


def dfs(node, weight):
    for data in graph[node]:
        if data[0] not in used:
            used.append(data[0])
            dfs(data[0], weight + data[1])
    ans_list[node] = weight


used = [k]
dfs(k, 0)

for _ in range(q):
    a, b = map(lambda x: int(x) - 1, input().split())
    print(ans_list[a] + ans_list[b])

Submission status: Time Limit Exceeded

Solution code:
# disjoint setかと思いきやDFS
# どこが悪いのかさっっっっっっぱりわからん...
# あ 再帰にしてるからその上限か
import sys

sys.setrecursionlimit(10000000)

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

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

q, k = map(int, input().split())
k = k - 1
# kからスタートしてぜんぶたどる
ans_list = [0 for _ in range(n)]


def dfs(node, used, weight):
    for data in graph[node]:
        if data[0] not in used:
            next_used = used[:]
            next_used.append(data[0])
            dfs(data[0], next_used, weight + data[1])
    ans_list[node] = weight


dfs(k, [k], 0)

for _ in range(q):
    a, b = map(lambda x: int(x) - 1, input().split())
    print(ans_list[a] + ans_list[b])

Submission status: Time Limit Exceeded

Solution code:
# KからDFS -> xからKまでとyからKまで

import sys
sys.setrecursionlimit(10**8)

n = int(input())
graph = [[] for _ in range(n)]
costs = [0 for _ in range(n)]

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


def dfs(cur, cost, p):
    for g in graph[cur]:
        if g[0] != p and costs[g[0]] == 0:
            costs[g[0]] = g[1] + cost
            dfs(g[0], costs[g[0]], cur)


dfs(k - 1, 0, -1)

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

Submission status: Time Limit Exceeded

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

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

graph = [[0]*N for _ in range(N)]

for _ in range(N-1):
    a, b, c = map(int, sys.stdin.buffer.readline().split())
    graph[a-1][b-1] = c
    graph[b-1][a-1] = c

Q, K = map(int, sys.stdin.buffer.readline().split())
dist_K = dijkstra(graph, indices = K-1)

ans = []
for _ in range(Q):
    x, y = map(int, sys.stdin.buffer.readline().split())
    ans.append(int(dist_K[x-1] + dist_K[y-1]))

print("\n".join(map(str, ans)))

Submission status: Time Limit Exceeded

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

n = int(input())
l = [[0]*n for _ in range(n)]
for _ in range(n-1):
  a, b, c = map(int, input().split())
  l[a-1][b-1] = c
  l[b-1][a-1] = c
csr = csr_matrix(l)
q, k = map(int, input().split())
A = dijkstra(csr, indices=k-1)
for _ in range(q):
  x, y = map(int, input().split())
  print(int(A[x-1] + A[y-1]))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

from heapq import heappop, heappush

def main():
    cost = dict()
    for _ in range(n - 1):
        a, b, c = map(int, input().split())
        if a - 1 in cost:
            cost[a-1] = cost[a-1] + [(b-1, c)]
        else:
            cost[a-1] = [(b-1, c)]
        if b - 1 in cost:
            cost[b-1] = cost[b-1] + [(a-1, c)]
        else:
            cost[b-1] = [(a-1, c)]

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

    start = K - 1
    d = [float('inf') for i in range(n)] # 最短距離
    d[start] = 0

    q = [] # min-heap, (距離, 頂点)
    heappush(q, (d[start], start))
    while q:
        du, u = heappop(q) # 最短距離とその頂点
        if d[u] < du:
            continue
        if u in cost:
            for v, weight in cost[u]:
                alt = du + weight
                if d[v] > alt:
                    d[v] = alt
                    heappush(q, (alt, v))

    for _ in range(Q):
        goal1, goal2 = map(int, input().split())
        print(d[goal1 - 1] + d[goal2 - 1])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
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)]

from heapq import heappop, heappush

def main():
    cost = dict()
    for a, b, c in abc:
        if a-1 in cost:
            cost[a-1] = cost[a-1] + [(b-1, c)]
        else:
            cost[a-1] = [(b-1, c)]
        if b-1 in cost:
            cost[b-1] = cost[b-1] + [(a-1, c)]
        else:
            cost[b-1] = [(a-1, c)]

    start = K - 1
    d = [float('inf') for i in range(n)] # 最短距離
    d[start] = 0

    q = [] # min-heap, (距離, 頂点)
    heappush(q, (d[start], start))
    while q:
        du, u = heappop(q) # 最短距離とその頂点
        if d[u] < du:
            continue
        if u in cost:
            for v, weight in cost[u]:
                alt = du + weight
                if d[v] > alt:
                    d[v] = alt
                    heappush(q, (alt, v))

    for goal1, goal2 in xy:
        print(d[goal1 - 1] + d[goal2 - 1])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
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)]

from heapq import heappop, heappush

def main():
    cost = dict()
    for a, b, c in abc:
        if a-1 in cost:
            cost[a-1] = cost[a-1] + [(b-1, c)]
        else:
            cost[a-1] = [(b-1, c)]
        if b-1 in cost:
            cost[b-1] = cost[b-1] + [(a-1, c)]
        else:
            cost[b-1] = [(a-1, c)]

    start = K - 1
    d = [float('inf') for i in range(n)] # 最短距離
    d[start] = 0

    q = [] # min-heap, (距離, 頂点)
    heappush(q, (d[start], start))
    while q:
        du, u = heappop(q) # 最短距離とその頂点
        if d[u] < du:
            continue
        for v, weight in cost.get(u, []):
            alt = du + weight
            if d[v] > alt:
                d[v] = alt
                heappush(q, (alt, v))

    for goal1, goal2 in xy:
        print(d[goal1 - 1] + d[goal2 - 1])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
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)]

mp2 = []
for i in range(len(abc)):
    mp2.append([abc[i][0] - 1, abc[i][1] - 1, abc[i][2]])
    mp2.append([abc[i][1] - 1, abc[i][0] - 1, abc[i][2]])
n_v = n
start = K - 1


# main
# コストテーブルの作成
from heapq import heappop, heappush
inf = float('inf')
prev = [None] * n_v # 経路をたどるときに使う
cost = dict() # コストテーブル
for i, j, k in mp2:
    cost[i] = cost.get(i, []) + [(j, k)]
# print(cost)

d = [inf for i in range(n_v)] # 最短距離
d[start] = 0

q = [] # min-heap, (距離, 頂点)
heappush(q, (d[start], start))
while q:
    # print(q, d, prev)
    du, u = heappop(q) # 最短距離とその頂点
    if d[u] < du:
        continue
    for v, weight in cost.get(u, []):
        alt = du + weight
        if d[v] > alt:
            d[v] = alt
            prev[v] = u
            heappush(q, (alt, v))

for i in range(Q):
    goal1 = xy[i][0] - 1
    goal2 = xy[i][1] - 1

    print(d[goal1] + d[goal2])

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
dist=[[-1 for i in range(n)] for i in range(n)]
for i in range(n-1):
  dist[i][i]=0
  a,b,c=map(int,input().split())
  dist[a-1][b-1]=c
  dist[b-1][a-1]=c

Q,K=map(int,input().split())
distFromK=[-1 for i in range(n)]

# start from K
stack=[]
stack.append([K-1,0,-1])
while stack:
  node=stack.pop()
  num=node[0]
  d=node[1]
  parent=node[2]
  if distFromK[num]==-1:
    distFromK[num]=d
  else:
    distFromK[num]=min(d,distFromK[num])
  targets=dist[num]
  for i in range(len(targets)):
    if i==parent or i==num:
      continue
    if targets[i]==-1:
      continue
    stack.append([i,targets[i]+d,num])
    
for i in range(Q):
  x,y=map(int,input().split())
  print(distFromK[x-1]+distFromK[y-1])

Submission status: Time Limit Exceeded

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


def BFS(x, y):
    visited = [False for _ in range(N+1)]
    next_N = [False for _ in range(N+1)]
    INF = float('inf')
    dest = [INF for _ in range(N+1)]
    d = deque()
    visited[x] = True
    dest[x] = 0
    for B, C in edge[x]:
        d.append([B, C])
        next_N[B] = True
        dest[B] = dest[x] + C
    while d:
        now = d.popleft()
        visited[now[0]] = True
        for B, C in edge[now[0]]:
            if visited[B] == False and next_N[B] == False:
                d.append([B, C])
                next_N[B] = True
                dest[B] = dest[now[0]] + C
    return dest[y]

Q, K = map(int, input().split())
xy = [list(map(int, input().split())) for _ in range(Q)]
for X, Y in xy:
    print(BFS(X, K) + BFS(K, Y))

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heappop, heappush
input = sys.stdin.readline

def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])
def graphm():
    n=inp()
    g=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b,w=inpm()
        a-=1
        b-=1
        g[a].append((b,w))
        g[b].append((a,w))
    return n,g
def dijkstra(s,to,n,g): # sからの最短距離 頂点数n
    s -= 1
    que = []
    d = [10**15 for _ in range(n)]
    d[s] = 0
    heappush( que,(0,s) )
    while len(que)>0:
        p =  heappop(que)
        v = p[1]
        if d[v] < p[0]:
            if p[1]==to-1:
                break
            continue
        for i in range(len(g[v])):
            edge = g[v][i]
            if d[edge[0]] > d[v] + edge[1]:
                d[edge[0]] = d[v] + edge[1]
                heappush( que,(d[edge[0]] , edge[0]) )
    return d[to-1]

def dijkstra1(s,n,g): # sからの最短距離 頂点数n
    s -= 1
    que = []
    d = [10**15 for _ in range(n)]
    d[s] = 0
    heappush( que,(0,s) )
    while len(que)>0:
        p =  heappop(que)
        v = p[1]
        if d[v] < p[0]:
            continue
        for i in range(len(g[v])):
            edge = g[v][i]
            if d[edge[0]] > d[v] + edge[1]:
                d[edge[0]] = d[v] + edge[1]
                heappush( que,(d[edge[0]] , edge[0]) )
    return d

def main():
    n,graph = graphm()
    q,k = inpm()
    pre = dijkstra1(k,n,graph)
    for _ in range(q):
        x,y = inpm()
        print( dijkstra(x,k,n,graph) + pre[y-1] )    

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heappop, heappush
input = sys.stdin.readline

def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])
def graphm():
    n=inp()
    g=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b,w=inpm()
        a-=1
        b-=1
        g[a].append((b,w))
        g[b].append((a,w))
    return n,g
def dijkstra(s,to,n,g): # sからの最短距離 頂点数n
    s -= 1
    que = []
    d = [10**15 for _ in range(n)]
    d[s] = 0
    heappush( que,(0,s) )
    while len(que)>0:
        p =  heappop(que)
        v = p[1]
        if d[v] < p[0]:
            continue
        for i in range(len(g[v])):
            edge = g[v][i]
            if d[edge[0]] > d[v] + edge[1]:
                d[edge[0]] = d[v] + edge[1]
                heappush( que,(d[edge[0]] , edge[0]) )
    return d[to-1]

def dijkstra1(s,n,g): # sからの最短距離 頂点数n
    s -= 1
    que = []
    d = [10**15 for _ in range(n)]
    d[s] = 0
    heappush( que,(0,s) )
    while len(que)>0:
        p =  heappop(que)
        v = p[1]
        if d[v] < p[0]:
            continue
        for i in range(len(g[v])):
            edge = g[v][i]
            if d[edge[0]] > d[v] + edge[1]:
                d[edge[0]] = d[v] + edge[1]
                heappush( que,(d[edge[0]] , edge[0]) )
    return d

def main():
    n,graph = graphm()
    q,k = inpm()
    pre = dijkstra1(k,n,graph)
    for _ in range(q):
        x,y = inpm()
        print( dijkstra(x,k,n,graph) + pre[y-1] )    

if __name__ == "__main__":
    main()