Buggy python submission (verdict: Runtime Error):
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 scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

def main():
    cost = [[0] * n for _ in range(n)]

    for i in range(len(abc)):
        a = abc[i][0] - 1
        b = abc[i][1] - 1
        c = abc[i][2]
        cost[a][b] = c

    graph = csr_matrix(cost)
    dist_matrix = dijkstra(csgraph=graph, directed=False, indices=K-1, return_predecessors=False)

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

if __name__ == '__main__':
    main()


Fixed submission:
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 = [[] for _ in range(n)]
    for i in range(n - 1):
        a = abc[i][0] - 1
        b = abc[i][1] - 1
        c = abc[i][2]
        cost[a].append((b, c))
        cost[b].append((a, c))
    # print(cost)

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

Buggy python submission (verdict: Time Limit Exceeded):
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()


Fixed submission:
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 = [[] for _ in range(n)]
    for i in range(n - 1):
        a = abc[i][0] - 1
        b = abc[i][1] - 1
        c = abc[i][2]
        cost[a].append((b, c))
        cost[b].append((a, c))
    # print(cost)

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

Buggy python submission (verdict: Time Limit Exceeded):
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()


Fixed submission:
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 = [[] for _ in range(n)]
    for i in range(n - 1):
        a = abc[i][0] - 1
        b = abc[i][1] - 1
        c = abc[i][2]
        cost[a].append((b, c))
        cost[b].append((a, c))
    # print(cost)

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

Buggy python submission (verdict: Time Limit Exceeded):
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()


Fixed submission:
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 = [[] for _ in range(n)]
    for i in range(n - 1):
        a = abc[i][0] - 1
        b = abc[i][1] - 1
        c = abc[i][2]
        cost[a].append((b, c))
        cost[b].append((a, c))
    # print(cost)

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

Buggy python submission (verdict: Time Limit Exceeded):
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])


Fixed submission:
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 = [[] for _ in range(n)]
    for i in range(n - 1):
        a = abc[i][0] - 1
        b = abc[i][1] - 1
        c = abc[i][2]
        cost[a].append((b, c))
        cost[b].append((a, c))
    # print(cost)

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

Buggy python submission (verdict: Time Limit Exceeded):
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])


Fixed submission:
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 = [[] for _ in range(n)]
    for i in range(n - 1):
        a = abc[i][0] - 1
        b = abc[i][1] - 1
        c = abc[i][2]
        cost[a].append((b, c))
        cost[b].append((a, c))
    # print(cost)

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