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

Solution code:
import heapq
N = int(input())
E = [[] for _ in range(N+1)]
for _ in range(N-1):
    ta,tb,tc = map(int, input().split())
    E[ta].append([tc,tb])
    E[tb].append([tc,ta])

Q, K = map(int, input().split())
inf = float('inf')
D = [inf] * (N+1)

q = []
heapq.heappush(q,[0,K])
cnt = 0
while True:
    d, cp = heapq.heappop(q)
    if D[cp] != inf:
        continue
    else:
        D[cp] = d
        cnt += 1
        if cnt == N:
            break

        for nd,np in E[cp]:
            heapq.heappush(q,[D[cp]+nd, np])

ans = []
for _ in range(Q):
    ts,tg = map(int, input().split())
    ans.append(D[ts]+D[tg])

for a in ans:
    print(a)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
mod2 = 2 ** 61 + 1
from collections import deque
import heapq
from bisect import bisect_left, insort_left, bisect_right

_NUMINT_ALL = list(range(10))


def main():
    ans = solve()

    if ans is True or ans is False:
        YesNo(ans)
    elif ans is not None:
        print(ans)


def solve():
    N = iip(False)
    edge = {}
    for i in range(N):
        edge[i] = []

    for i in range(N-1):
        a, b, c = iip()
        a -= 1
        b -= 1
        edge[a].append((b, c))
        edge[b].append((a, c))

    Q, K = iip()

    q = []
    for i in range(Q):
        q.append(iip())

    que = deque()
    que.append(K-1)
    distanse = [False for i in range(N)]
    distanse[K-1] = 0
    while que:
        node = que.popleft()
        dis = distanse[node]

        for next, c in edge[node]:
            if distanse[next] is not False:
                continue
            distanse[next] = dis + c
            que.append(next)

    #print(distanse)

    ans = []
    for i, j in q:
        ans.append(distanse[i-1]+distanse[j-1])

    split_print_enter(ans)




#####################################################ライブラリ集ここから

def iip(listed=True, num_only=True):  # 数字のinputをlistで受け取る
    if num_only:
        ret = [int(i) for i in input().split()]
    else:
        ret = [int(i) if i in _NUMINT_ALL else i for i in input().split()]

    if len(ret) == 1 and not listed:
        return ret[0]
    return ret


def saidai_kouyakusuu(A):  # 最大公約数
    l = len(A)
    while True:
        m = min(A)
        mx = max(A)
        if m == mx:
            return m

        for i in range(l):
            if A[i] % m == 0:
                A[i] = m
            else:
                A[i] %= m


def sort_tuples(l, index):  # タプルのリストを特定のインデックスでソートする
    if isinstance(l, list):
        l.sort(key=lambda x: x[index])
        return l
    else:
        l = list(l)
        return sorted(l, key=lambda x: x[index])


def count_elements(l):  # リストの中身の個数を種類分けして辞書で返す
    d = {}
    for i in l:
        if i in d:
            d[i] += 1
        else:
            d[i] = 1
    return d


def safeget(l, index, default="exception"):  # listの中身を取り出す時、listからはみ出たり
    if index >= len(l):                      # マイナスインデックスになったりするのを防ぐ
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。配列の長さは", len(l), "です"]))
        else:
            return default
    elif index < 0:
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。負の値は許可されていません"]))
        else:
            return default
    else:
        return l[index]


def iipt(l, listed=False, num_only=True):  # 縦向きに並んでいるデータをリストに落とし込む(iip利用)
    ret = []
    for i in range(l):
        ret.append(iip(listed=listed, num_only=num_only))
    return ret


def sortstr(s):  # 文字列をソートする
    return "".join(sorted(s))


def iip_ord(startcode="a"):  # 文字列を数字の列に変換する(数字と文字は1:1対応)
    if isinstance(startcode, str):
        startcode = ord(startcode)
    return [ord(i) - startcode for i in input()]


def YesNo(s):  # TrueFalseや1, 0をYesNoに変換する
    if s:
        print("Yes")
    else:
        print("No")


def fprint(s):  # リストを平たくしてprintする(二次元リストを見やすくしたりとか)
    for i in s:
        print(i)


def bitall(N):  # ビット全探索用のインデックスを出力
    ret = []
    for i in range(2 ** N):
        a = []
        for j in range(N):
            a.append(i % 2)
            i //= 2
        ret.append(a)
    return ret

def split_print_space(s):  # リストの中身をスペース区切りで出力する
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):  # リストの中身を改行区切りで出力する
    print("\n".join([str(i) for i in s]))


def soinsuu_bunkai(n):  # 素因数分解
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):  # nCrをmodを使って計算する
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):  #  modnにおける逆元を計算
    return power(n, mod - 2)


def power(n, p, mod_=mod):  # 繰り返し二乗法でn**p % modを計算
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
def main():
    n = int(input())
    a = []
    b = []
    c = []
    lst = [[] for _ in range(n)]

    for i in range(n - 1):
        aa, bb, cc = map(int,input().split())
        lst[aa - 1].append((bb - 1, cc))
        lst[bb - 1].append((aa - 1, cc))

    q, k = map(int,input().split())
    x = []
    y = []
    for i in range(q):
        xx, yy = map(int,input().split())
        x.append(xx - 1)
        y.append(yy - 1)
    qq = deque()
    qq.append(k - 1)
    dist = [0] * n
    while len(qq) != 0:
        now = qq.popleft()
        for to, w in lst[now]:
            if dist[to] != 0:
                continue
            dist[to] = dist[now] + w
            qq.append(to)

    for i in range(q):
        print(dist[x[i]] + dist[y[i]])





if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import queue
def main():
    n = int(input())
    a = []
    b = []
    c = []
    lst = [[] for _ in range(n)]

    for i in range(n - 1):
        aa, bb, cc = map(int,input().split())
        lst[aa - 1].append((bb - 1, cc))
        lst[bb - 1].append((aa - 1, cc))

    q, k = map(int,input().split())
    x = []
    y = []
    for i in range(q):
        xx, yy = map(int,input().split())
        x.append(xx - 1)
        y.append(yy - 1)
    qq = queue.Queue()
    qq.put(k - 1)
    dist = [0] * n
    while not qq.empty():
        now = qq.get()
        for to, w in lst[now]:
            if dist[to] != 0:
                continue
            dist[to] = dist[now] + w
            qq.put(to)

    for i in range(q):
        print(dist[x[i]] + dist[y[i]])





if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

n = int(input())
adj = [[] for _ in range(n)]  # adjacence(隣接)の略

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

q, k = map(int, input().split())
k -= 1
dist = [-1]*n  # 経由地から各頂点までのコスト
dist[k] = 0  # 経由地kをスタート地点とするため、コスト0に設定

stack = [k]  # 探索候補。経由地kをスタート地点にするため、先に積んでおく

while stack: # 探索候補がなくなるまで続ける
    now = stack.pop()
    for dest, cost in adj[now]:
        if dist[dest] != -1: # dest(目的地)までのコストがすでに設定されていればスルー
            continue
        dist[dest] = dist[now] + cost # コストを現地点までのコストと合算して算出
        stack.append(dest)

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

Submission status: Accepted

Solution code:
n = int(input())
adj = [[] for _ in range(n)]  # adjacence(隣接)の略

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

q, k = map(int, input().split())
k -= 1
dist = [-1]*n  # 経由地から各頂点までのコスト
dist[k] = 0  # 経由地kをスタート地点とするため、コスト0に設定

stack = [k]  # 探索候補。経由地kをスタート地点にするため、先に積んでおく

while stack: # 探索候補がなくなるまで続ける
    now = stack.pop()
    for dest, cost in adj[now]:
        if dist[dest] != -1: # dest(目的地)までのコストがすでに設定されていればスルー
            continue
        dist[dest] = dist[now] + cost # コストを現地点までのコストと合算して算出
        stack.append(dest)

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

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
g = [[] for _ in range(n)]
cost = dict()
for i in range(n-1):
    a,b,c = inpl()
    a -= 1; b -= 1
    g[a].append(b); g[b].append(a)
    cost[(a,b)] = c; cost[(b,a)] = c
Q,k = inpl()
k -= 1
q = deque()
q.append(k)
dist = [-1] * n
dist[k] = 0
while q:
    v = q.popleft()
    for nv in g[v]:
        if dist[nv] != -1:
            continue
        dist[nv] = dist[v] + cost[(nv,v)]
        q.append(nv)
for _ in range(Q):
    a,b = inpl()
    print(dist[a-1] + dist[b-1])

Submission status: Accepted

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


N = int(input())
abc=[]
for _ in range(N-1):
    abc.append(tuple(map(int, input().split())))
Q, K = map(int, input().split())
xy=[]
for _ in range(Q):
    xy.append(tuple(map(int, input().split())))
#print(abc)
#print(xy)

G = [[] for _ in range(N+1)]
for el in abc:
    a,b,c = el
    G[a].append((b,c))
    G[b].append((a,c))
#print(G)

seen=[False]*(N+1)
distance=[0]*(N+1)
def dfs(n):
    seen[n]=True
    for el in G[n]:
        if seen[el[0]] == False:
            distance[el[0]] = distance[n] + el[1]
            dfs(el[0])
dfs(K)
#print(distance)

for q in xy:
    print(distance[q[0]]+distance[q[1]])

Submission status: Accepted

Solution code:
from collections import deque


def main():
    n = int(input())
    tree = [[] for _ in range(n)]
    dist = [0 for _ in range(n)]
    for _ 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])
    q, k = map(int, input().split())
    k -= 1
    s = deque([k])
    dist[k] = -1
    while s:
        now = s.pop()
        for t, d in tree[now]:
            if dist[t] == 0:
                dist[t] = dist[now] + d
                dist[t] += 1 if now == k else 0
                s.append(t)
    dist[k] = 0
    for _ in range(q):
        x, y = map(lambda x: int(x) - 1, input().split())
        print(dist[x] + dist[y])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    G=[[] for _ in range(N)]
    for _ in range(N-1):
        a,b,c=map(int, input().split())
        a,b=a-1,b-1
        G[a].append((b,c))
        G[b].append((a,c))
    Q,K=map(int, input().split())
    K-=1

    dfromK = [-1] * N
    dfromK[K] = 0
    stk = [(K,0)]
    while stk:
        v,d=stk.pop()
        for to,c in G[v]:
            if dfromK[to] >= 0: continue
            dfromK[to] = d+c
            stk.append((to,d+c))

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())

edges = [[] for _ in range(N)]
for _ in range(N - 1):
    fr, to, cost = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append((to, cost))
    edges[to].append((fr, cost))

Q, K = map(int, input().split())
K -= 1
ST = [tuple(map(lambda a: int(a) - 1, input().split())) for _ in range(Q)]


minDist = [10**18] * N
st = [(K, 0, -1)]
while st:
    now, d, pr = st.pop()
    minDist[now] = d
    for to, cost in edges[now]:
        if to == pr:
            continue
        st.append((to, d + cost, now))

ans = []
for s, t in ST:
    ans.append(minDist[s] + minDist[t])
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
from heapq import heappop,heappush
N = int(input())
G = [[] for _ in range(N)]
for _ in range(N - 1):
    a,b,c = map(int, input().split())
    G[a-1].append({"to":b-1, "cost":c})
    G[b-1].append({"to":a-1, "cost":c})
Q,K = map(int, input().split())
K -= 1

dist = [float("inf")] * N
dist[K] = 0
que = [(0, K)]

while que:
    d,v = heappop(que)
    if dist[v] < d: continue
    for e in G[v]:
        if dist[e["to"]] > d + e["cost"]:
            dist[e["to"]] = d + e["cost"]
            heappush(que, (dist[e["to"]], e["to"]))

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

n = int(input())
#O(ElogV)
import heapq
def dijkstra_heap(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

################################
n,w = n, n - 1

edge = [[] for i in range(n)]
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(w):
    x,y,z = map(int,input().split())
    edge[x - 1].append([z,y - 1])
    edge[y - 1].append([z,x - 1]) 

q, k = [int(x) for x in input().split()]

k_dis = dijkstra_heap(k - 1)

for _ in range(q):
    s, g = [int(x) for x in input().split()]
    print(k_dis[s - 1] + k_dis[g - 1])

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    from heapq import heappop, heappush
    N = int(input())
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        a, b, c = (int(i) for i in input().split())
        edge[a-1].append((c, b-1))
        edge[b-1].append((c, a-1))

    def dijkstra(G, s):
        d = [10**12]*N
        used = [True] * N  # True:未確定
        d[s] = 0
        used[s] = False
        edges = []
        for e in G[s]:
            heappush(edges, e)
        while len(edges):
            c, v = heappop(edges)
            if not used[v]:
                continue
            d[v] = c
            used[v] = False
            for nexc, nexv in G[v]:
                if used[nexv]:
                    heappush(edges, (nexc+c, nexv))
        return d

    Q, K = (int(i) for i in input().split())
    dist = dijkstra(edge, K-1)
    for q in range(Q):
        x, y = (int(i)-1 for i in input().split())
        print(dist[x] + dist[y])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    N = int(input())
    Edge = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b, c = map(int, input().split())
        Edge[a-1].append((b-1, c))
        Edge[b-1].append((a-1, c))
    Q, K = map(int, input().split())
    q = deque()
    Dist = [-1] * N
    q.append((K-1, K-1, 0))
    while q:
        nowN, preN, nD = q.popleft()
        if Dist[nowN] == -1:
            Dist[nowN] = nD
            for e, add in Edge[nowN]:
                if e != preN: q.append((e, nowN, nD + add))
    Ans = [None] * Q
    for i in range(Q):
        x, y = map(int, input().split())
        Ans[i] = str(Dist[x-1] + Dist[y-1])
    print("\n".join(Ans))

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

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

import heapq
INF = 10**18
def dijkstra_heap(s, edge):
    d = [INF] * n
    used = [True] * n #True: not used
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v],e[1]))
    return d

d = dijkstra_heap(k, edge)
#print(d)

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

Submission status: Accepted

Solution code:
N = int(input())
ABC = [tuple(map(int,input().split())) for i in range(N-1)]
Q,K = map(int,input().split())
K -= 1
XY = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(Q)]
es = [[] for i in range(N)]
for a,b,c in ABC:
    a,b = a-1,b-1
    es[a].append((b,c))
    es[b].append((a,c))
INF = float('inf')
dist = [INF] * N
dist[K] = 0
import heapq
hq = [(0,K)]
heapq.heapify(hq)
while hq:
    c,v = heapq.heappop(hq)
    for to,d in es[v]:
        if c+d >= dist[to]: continue
        dist[to] = c+d
        heapq.heappush(hq,(c+d,to))
ans = []
for x,y in XY:
    ans.append(dist[x]+dist[y])
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import sys
from collections import deque


IN = sys.stdin.readlines()
N = int(IN[0])

edge = [[] for _ in range(N)]
for i in range(1, N):
    a, b, c = map(int, IN[i].split())
    a -= 1; b -= 1
    edge[a].append((b, c))
    edge[b].append((a, c))

Q, K = map(int, IN[N].split())

q = deque()
path = [float('inf')] * N
path[K - 1] = 0
q.append((K - 1, 0))
while q:
    p, step = q.popleft()
    for np, d in edge[p]:
        if path[np] > step + d:
            q.append((np, step + d))
            path[np] = step + d

for i in range(N + 1, N + 1 + Q):
    x, y = map(int, IN[i].split())
    x -= 1; y -= 1
    Kx = path[x]
    Ky = path[y]
    print(Kx + Ky)

Submission status: Accepted

Solution code:
import heapq
import sys
input=sys.stdin.readline


def dijkstra(s):
    inf=float("inf")
    color=["white" for _ in range(n)]
    D=[inf for _ in range(n)]

    M=[[] for _ in range(n)]
    for a,b,c in ABC:
        M[a-1].append([b-1,c])
        M[b-1].append([a-1,c])

    D[s]=0

    H=[(0,s)]
    heapq.heapify(H)

    while len(H)>=1:
        u=heapq.heappop(H)[1]
        if color[u]=="black":continue
        color[u]="black"

        V=[(i,j) for i,j in M[u] if color[i]!="black"]
        while len(V)!=0:
            for i,j in V:
                if D[u]+j<D[i]:
                    D[i]=D[u]+j
                    color[i]="gray"
                    heapq.heappush(H,(D[i],i))
            break

    return D


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)]
D=dijkstra(k-1)
for x,y in XY:
    print(D[x-1]+D[y-1])

Submission status: Accepted

Solution code:
import heapq


def dijkstra(s):
    inf=float("inf")
    color=["white" for _ in range(n)]
    D=[inf for _ in range(n)]

    M=[[] for _ in range(n)]
    for a,b,c in ABC:
        M[a-1].append([b-1,c])
        M[b-1].append([a-1,c])

    D[s]=0

    H=[(0,s)]
    heapq.heapify(H)

    while len(H)>=1:
        u=heapq.heappop(H)[1]
        if color[u]=="black":continue
        color[u]="black"

        V=[(i,j) for i,j in M[u] if color[i]!="black"]
        while len(V)!=0:
            for i,j in V:
                if D[u]+j<D[i]:
                    D[i]=D[u]+j
                    color[i]="gray"
                    heapq.heappush(H,(D[i],i))
            break

    return D


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)]
D=dijkstra(k-1)
for x,y in XY:
    print(D[x-1]+D[y-1])

Submission status: Accepted

Solution code:
n=int(input())
g=[[] for i in range(n)]
for _ in range(n-1):
  u,v,c=map(int,input().split())
  g[u-1].append((v-1,c))
  g[v-1].append((u-1,c))
Q,k=map(int,input().split())
d=[-1]*n
d[k-1]=0
q=[k-1]
while q:
  t=q.pop()
  for x,cost in g[t]:
    if d[x]==-1:
      d[x]=d[t]+cost
      q.append(x)
for _ in range(Q):
  x,y=map(int,input().split())
  print(d[x-1]+d[y-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n= int(input())
bd = [[] for _ in range(n)]
for i in range(n-1):
    a,b,c= map(int,input().split())
    bd[a-1].append((b-1,c))
    bd[b-1].append((a-1,c))
q,k= map(int,input().split())
cost = [0] * n
def dfs(curnode,pre,addcost):
    for abr in bd[curnode]:
        if abr[0]!=pre:
            cost[abr[0]]=addcost+abr[1]
            dfs(abr[0],curnode,addcost+abr[1])
dfs(k-1,-1,0)
for i in range(q):
    x,y= map(int,input().split())
    print(cost[x-1]+cost[y-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n = int(input())
es=[[] for _ in range(n)] 
d = [0]*n 
used=[True]*n
for i in range(n-1):
    a,b,c = map(int,input().split())
    a,b = a-1, b-1
    es[a].append((b,c))
    es[b].append((a,c))


def dfs(s,dist):
    used[s]=False
    for v,x in es[s]:
        if used[v]:
            d[v]=dist+x
            dfs(v,dist+x)
q,k=map(int,input().split())
dfs(k-1,0)
for i in range(q):
    x,y=map(int,input().split())
    print(d[x-1]+d[y-1])

Submission status: Accepted

Solution code:


from collections import deque


def submit():
    n = int(input())
    edges = {i: [] for i in range(n)}
    for _ in range(n - 1):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        edges[a].append((b, c))
        edges[b].append((a, c))
    
    q, k = map(int, input().split())
    k -= 1
    # kからの距離を求める
    dist = [-1 for _ in range(n)]
    s = deque()
    s.append((k, 0))
    while len(s):
        e, d = s.pop()
        for neignbor, cost in edges[e]:
            if dist[neignbor] < 0:
                dist[neignbor] = d + cost
                s.append((neignbor, d + cost))

    # クエリを処理
    res = []
    for _ in range(q):
        x, y = map(int, input().split())
        x -= 1
        y -= 1
        res.append(dist[x] + dist[y])

    for r in res:
        print(r)


submit()

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
d = [[] for i in range(n)]
for i in range(n-1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    d[a].append([b,c])
    d[b].append([a,c])
q, k = map(int, input().split())
k -= 1

def bfs():
    d2 = [True] * n
    ans = [0] * n
    que = deque([k])
    d2[k] = False
    while len(que) != 0:
        val = que.popleft()

        for i in range(len(d[val])):
            if d2[d[val][i][0]] == True:
                que.append(d[val][i][0])
                ans[d[val][i][0]] += (ans[val] + d[val][i][1])
                d2[d[val][i][0]] = False
    return ans
ans = bfs()
for i in range(q):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    print(ans[x] + ans[y])

Submission status: Accepted

Solution code:
N = int(input())
D = {i: [] for i in range(N)}
DD = {}
L = [list(map(int, input().split())) for _ in range(N-1)]
Q, K = map(int, input().split())
dist = [-1 for i in range(N)]
for i in range(N-1):
  D[L[i][0]-1].append(L[i][1]-1)
  D[L[i][1]-1].append(L[i][0]-1)
  DD[(L[i][0]-1)*N+L[i][1]-1], DD[(L[i][1]-1)*N+L[i][0]-1] = L[i][2], L[i][2]
dist[K-1] = 0
p = [K-1]
while p != []:
  n = len(p)
  for i in range(n):
    q = p[i]
    X = D[q][:]
    for j in X:
      if dist[j] < 0:
        dist[j] = dist[q] + DD[q*N+j]
        p.append(j)
  p = p[n:]
for i in range(Q):
  x, y = map(int, input().split())
  print(dist[x-1] + dist[y-1])

Submission status: Accepted

Solution code:
from heapq import heappush,heapify,heappop
import sys
input = sys.stdin.readline
INF = 10**18

n = int(input())

es=[[] for _ in range(n)] # es[i] = (頂点iの(隣接する頂点,コスト)の組)
d = [INF]*n # 頂点sからの最短距離

# 入力
for i in range(n-1):
    a,b,c = map(int,input().split())
    a,b = a-1, b-1
    es[a].append((b,c))
    es[b].append((a,c))


def dijkstra(s):
    v = -1
    que = [(0,s)]
    heapify(que)
    d[s] = 0
    while que:
        p = heappop(que)
        v = p[1]
        if d[v] < p[0]:
            continue
        for e in es[v]:
            if d[e[0]] > d[v] + e[1]:
                d[e[0]] = d[v] + e[1]
                heappush(que, (d[e[0]], e[0])) 
q,k=map(int,input().split())
dijkstra(k-1)
for i in range(q):
    x,y=map(int,input().split())
    print(d[x-1]+d[y-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n = int(input())
es=[[] for _ in range(n)] # es[i] = (頂点iの(隣接する頂点,コスト)の組)
d = [0]*n # 頂点sからの最短距離
used=[True]*n
# 入力
for i in range(n-1):
    a,b,c = map(int,input().split())
    a,b = a-1, b-1
    es[a].append((b,c))
    es[b].append((a,c))


def dfs(s,dist):
    used[s]=False
    for v,x in es[s]:
        if used[v]:
            d[v]=dist+x
            dfs(v,dist+x)
q,k=map(int,input().split())
dfs(k-1,0)
for i in range(q):
    x,y=map(int,input().split())
    print(d[x-1]+d[y-1])

Submission status: Accepted

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

import sys

def main():
    input = sys.stdin.readline
    n = int(input())
    adjs = [[] for i in range(n)]
    for i in range(n - 1):
        a, b, c = map(int, input().split())
        adjs[a - 1].append((b - 1, c))
        adjs[b - 1].append((a - 1, c))
    q, k = map(int, input().split())

    # DFS
    dist = [None] * n
    dist[k - 1] = 0
    hq = [(0, k - 1)]
    queued = [False] * n
    queued[k - 1] = True
    while hq:
        d, j = hq.pop()
        dist[j] = d
        for j2, d2 in adjs[j]:
            if queued[j2]:
                continue
            hq.append((d + d2, j2))
            queued[j2] = True

    # For each query
    for i in range(q):
        x, y = map(int, input().split())
        print(dist[x - 1] + dist[y - 1])

if __name__ == "__main__":
    main()

Submission status: Accepted

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

import sys
import heapq

def main():
    input = sys.stdin.readline
    n = int(input())
    adjs = [[] for i in range(n)]
    for i in range(n - 1):
        a, b, c = map(int, input().split())
        adjs[a - 1].append((b - 1, c))
        adjs[b - 1].append((a - 1, c))
    q, k = map(int, input().split())

    # Dijkstra
    dist = [None] * n
    dist[k - 1] = 0
    hq = [(0, k - 1)]
    queued = [False] * n
    queued[k - 1] = True
    while hq:
        d, j = heapq.heappop(hq)
        dist[j] = d
        for j2, d2 in adjs[j]:
            if queued[j2]:
                continue
            heapq.heappush(hq, (d + d2, j2))
            queued[j2] = True

    # For each query
    for i in range(q):
        x, y = map(int, input().split())
        print(dist[x - 1] + dist[y - 1])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions
from decimal import Decimal
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
co = dict()
g = [[] for _ in range(n)]
cost = [-1] * n
for i in range(n-1):
    a,b,c = inpl()
    a -= 1; b -= 1
    g[a] += [b]; g[b] += [a]
    co[(a,b)] = c; co[(b,a)] = c
Q,k = inpl()
k -= 1; cost[k] = 0
q = deque()
q.append(k)
while q:
    nv = q.popleft()
    for v in g[nv]:
        if cost[v] > 0:
            continue
        cost[v] = cost[nv] + co[(v,nv)]
        q.append(v)
for _ in range(Q):
    a,b = inpl()
    a -= 1; b -= 1
    print(cost[a] + cost[b])

Submission status: Accepted

Solution code:
n = int(input())
E = [[] for i in range(n)]
for i in range(n-1):
    ai,bi,ci = map(int, input().split( ))
    ai-=1;bi-=1
    E[ai].append((bi,ci))
    E[bi].append((ai,ci))

from collections import deque
Q = deque()

q,k = map(int, input().split( ))
k-=1
Q.append(k)
d = [-1]*n 
d[k] = 0
while Q:
    v = Q.popleft()
    for u,c in E[v]:
        if d[u]<0:
            d[u] = d[v]+c
            Q.append(u)

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

Submission status: Accepted

Solution code:
from collections import deque
N=int(input())
ver=[[] for i in range(N)] # (vertex,cost) in each vertex
for _ in range(N-1):
  a,b,c=map(int,input().split())
  ver[a-1].append((b-1,c))
  ver[b-1].append((a-1,c))

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

par=[-2 for i in range(N)]
par[K-1]=-1
q=deque([K-1])
while q:
    i=q.popleft()
    for j,c in ver[i]:
        if par[j]==-2:
            par[j]=i
            q.append(j)

cost=[-1 for i in range(N)]
cost[K-1]=0
stack=[[K-1,0]]
while stack:
    i,c=stack.pop()
    for j,d in ver[i]:
        if par[i]!=j:
            cost[j]=c+d
            stack.append([j,cost[j]])
# print(cost)
for _ in range(Q):
  x,y=map(int,input().split())
  print(cost[x-1]+cost[y-1])

Submission status: Accepted

Solution code:
from collections import deque
import heapq
N=int(input())
numbers=[[] for _ in range(N)]
for _ in range(N-1):
    a,b,c=map(int,input().split())
    a-=1
    b-=1
    numbers[a].append((b,c))
    numbers[b].append((a,c))
Q,K=map(int,input().split())
K-=1
keika=[]
for _ in range(Q):
    x,y=map(int,input().split())
    keika.append([x-1,y-1])
inf=pow(10,10)
visited=[inf for _ in range(N)]
visited[K]=0
stack=[K]
heapq.heapify(stack)
while len(stack)>0:
    n=heapq.heappop(stack)
    for s,t in numbers[n]:
        if visited[s]==inf:
            heapq.heappush(stack,s)
            visited[s]=visited[n]+t
for z in keika:
    print(visited[z[0]]+visited[z[1]])