Problem p03634 (python)

Fixed submission:
"""
--- アルゴリズム概要 ---
前計算で頂点Kから各ノードへの最短路を記録しておき、
各クエリに対しては、dp[a]+dp[b]を返せばよい。

頂点Kから各ノードへの最短ルートはdfsとかで記録していけばよい。
"""
def main():
    from collections import deque
    import sys
    sys.setrecursionlimit(20000000)
    input = sys.stdin.readline
    N = int(input())
    AB = [[]for _ in range(N+1)]
    for i in range(N-1):
        a,b,c = map(int,input().split())
        AB[a].append((b,c))
        AB[b].append((a,c))

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

    path = {K:""}
    dp = [0]*(N+1)
    que = deque()
    for n,c in AB[K]:
        que.append((n,c))
    while que:
        now,cost = que.pop()
        path[now]=""
        dp[now]=cost
        for n,c in AB[now]:
            if n not in path:
                que.append((n,cost+c))
    for i in range(Q):
        x,y=map(int,input().split())
        print(dp[x]+dp[y])
main()

Buggy submission (verdict: Runtime Error):
N = int(input())
edges = [{}for _ in range(N+1)]
for _ in range(N-1):
    a,b,c = map(int,input().split())
    edges[a][b] = c
    edges[b][a] = c

costDic = [0]*(N+1)
def f(cost,now,p):
    costDic[now] = cost
    for nx,c in edges[now].items():
        if nx != p:
            f(cost+c,nx,now)

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

Buggy submission (verdict: Runtime Error):
"""
--- アルゴリズム概要 ---
前計算で頂点Kから各ノードへの最短路を記録しておき、
各クエリに対しては、dp[a]+dp[b]を返せばよい。

頂点Kから各ノードへの最短ルートはdfsとかで記録していけばよい。
"""
def main():
    import sys
    sys.setrecursionlimit(2000000)
    input = sys.stdin.readline
    N = int(input())
    AB = [{}for _ in range(N+1)]
    for i in range(N-1):
        a,b,c = map(int,input().split())
        AB[a][b] = c
        AB[b][a] = c

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

    path = {K:""}
    dp = [0]*(N+1)
    def dfs(n,cost):
        path[n]=""
        dp[n]=cost
        for i,c in AB[n].items():
            if i not in path:
                nextcost = (cost+c)%mod
                dfs(i,nextcost)
    dfs(K,0)
    for i in range(Q):
        x,y=map(int,input().split())
        print(dp[x]+dp[y])
main()

Buggy submission (verdict: Runtime Error):
"""
--- アルゴリズム概要 ---
前計算で頂点Kから各ノードへの最短路を記録しておき、
各クエリに対しては、dp[a]+dp[b]を返せばよい。

頂点Kから各ノードへの最短ルートはdfsとかで記録していけばよい。
"""
def main():
    import sys
    sys.setrecursionlimit(20000000)
    input = sys.stdin.readline
    N = int(input())
    AB = [{}for _ in range(N+1)]
    for i in range(N-1):
        a,b,c = map(int,input().split())
        AB[a][b] = c
        AB[b][a] = c

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

    path = {K:""}
    dp = [0]*(N+1)
    def dfs(n,cost):
        path[n]=""
        dp[n]=cost
        for i,c in AB[n].items():
            if i not in path:
                nextcost = (cost+c)%mod
                dfs(i,nextcost)
    dfs(K,0)
    for i in range(Q):
        x,y=map(int,input().split())
        print(dp[x]+dp[y])
main()

Buggy submission (verdict: Runtime Error):
"""
--- アルゴリズム概要 ---
前計算で頂点Kから各ノードへの最短路を記録しておき、
各クエリに対しては、dp[a]+dp[b]を返せばよい。

頂点Kから各ノードへの最短ルートはdfsとかで記録していけばよい。
"""

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

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

path = {K:""}
dp = [0]*(N+1)
def dfs(n,cost):
    path[n]=""
    dp[n]=cost
    for i,c in AB[n].items():
        if i not in path:
            dfs(i,cost+c)
dfs(K,0)
for i in range(Q):
    x,y=map(int,input().split())
    print(dp[x]+dp[y])

Buggy submission (verdict: Runtime Error):
"""
---アルゴリズム概要---
閉路のないグラフなので、シンプルにxからKまでまっすぐに進んでから、Kからyにまっすぐ進むことを考えればよい。
クエリの数Qが10**5個あるので、ノードaからノードbにまっすぐ進む場合のコストをメモしていくのがよさそう。

次に、どうやってノードaからノードbへの「まっすぐ進む道」＝「まっすぐ進むための次のノード」を判断するかだが、
これは、ノードaが直接つながっているノードのうち、
ノードbへのコストが最も少ないものがまっすぐ進むための次のノードとなる。
"""

N = int(input())
edges = [{} for _ in range(N)]
#dpでiからjへの最短コストを管理する。
for _ in range(N-1):
    a,b,c = map(int,input().split())
    edges[a-1][b]=c
    edges[b-1][a]=c

Q,K = map(int,input().split())
dp = [float("INF")]*(N)

path = {}
def dfs(i,c):
    dp[i-1]=c
    path[i]=""
    for n,cost in edges[i-1].items():
        if n not in path:
            dfs(n, c + cost)

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