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:
N = int(input())

#隣接リスト
ad = {}
for n in range(N):
    ad[n+1]=[]
    
for n in range(N-1):
    a,b,c = list(map(int,input().split()))
    ad[a].append([b,c])
    ad[b].append([a,c])
    
Query = []
Q,K = list(map(int,input().split()))
for q in range(Q):
    x,y = list(map(int,input().split()))
    Query.append([x,y])

# ダイクストラ（優先度キュー）
import heapq
INF = 10 ** 10

color = {}
for n in range(N):
    color[n+1] = -1
    
dist = {}
for n in range(N):
    dist[n+1] = INF

def dijkstra(start, node_num): 
    HP = []
    dist[start] = 0

    heapq.heappush(HP,[start,0])

    while HP:
        u = heapq.heappop(HP)[0]

        color[u] = 1

        for to, cost in ad[u]:
            if color[to] == -1 and dist[u] + cost < dist[to]:
                dist[to] = dist[u] + cost
                heapq.heappush(HP, (to, dist[to]))
    return dist

start = K
node_num = N
dist = dijkstra(start, node_num)

for x,y in Query:
    print(dist[x]+dist[y])

Submission status: Wrong Answer

Solution code:
N = int(input())

#隣接リスト
ad = {}
for n in range(N):
    ad[n+1]=[]
    
for n in range(N-1):
    a,b,c = list(map(int,input().split()))
    ad[a].append([b,c])
    ad[b].append([a,c])
    
Query = []
Q,K = list(map(int,input().split()))
for q in range(Q):
    x,y = list(map(int,input().split()))
    Query.append([x,y])

# ダイクストラ（優先度キュー）
import heapq
INF = 10 ** 9

color = {}
for n in range(N):
    color[n+1] = -1
    
dist = {}
for n in range(N):
    dist[n+1] = INF

def dijkstra(start, node_num): 
    HP = []
    dist[start] = 0

    heapq.heappush(HP,[start,0])

    while HP:
        u = heapq.heappop(HP)[0]

        color[u] = 1

        for to, cost in ad[u]:
            if color[to] == -1 and dist[u] + cost < dist[to]:
                dist[to] = dist[u] + cost
                heapq.heappush(HP, (to, dist[to]))
    return dist

start = K
node_num = N
dist = dijkstra(start, node_num)

for x,y in Query:
    print(dist[x]+dist[y])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())
def NIJIGEN(H): return [list(input()) for i in range(H)]
def bfs(place,dis):
  for i in tree[place]:
    a,b=i
    if a not in finish:
      finish.add(a)
      disli[a]=dis+b
      bfs(a,dis+b)
N=INT()
tree=[[] for _ in range(N)]
for i in range(N-1):
  a,b,c=MAP()
  tree[a-1].append([b-1,c])
  tree[b-1].append([a-1,c])
Q,K=MAP()#処理
disli=[0 for i in range(N)]
finish=set()
bfs(K-1,0)

for i in range(Q):
  a,b=MAP()
  print(disli[a-1]+disli[b-1])

Submission status: Wrong Answer

Solution code:
import heapq
INF = 10**10
def dijkstra(s, g):
    dists  = [INF for i in range(n)]
    dists[s] = 0
    pq = [(0, s)] # 優先度付きキューのオブジェクトそのものはただのリスト
    while(pq):
        d, node = heapq.heappop(pq)
        if (d > dists[node]): # 探索の対象にする必要があるか確認
            continue
        for next, cost in adj[node]:
            if d + cost < dists[next]: # 更新すべきか確認
                dists[next] = d + cost
                heapq.heappush(pq, (dists[next],next))
    if dists[g] == INF:
        return -1
    else:
        return dists[g]
n=int(input())
adj = [[] for i in range(n)] # 隣接リスト

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

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

Submission status: Wrong Answer

Solution code:
import networkx as nx

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

G = nx.Graph()

for a, b, c in ABC:
    G.add_edge(a - 1, b - 1, weight=c)

# pred, dist = nx.dijkstra_predecessor_and_distance(G, K - 1)
dist = nx.shortest_path_length(G, K - 1)

for x, y in XY:
    print(dist[x - 1] + dist[y - 1])

Submission status: Wrong Answer

Solution code:

from collections import defaultdict,deque
import sys
finput=lambda: sys.stdin.readline().strip()

def main():
  n=int(finput())
  edges=[tuple(map(int,finput().split())) for _ in range(n-1)]
  q,k=map(int,finput().split())
  xy=[tuple(map(int,finput().split())) for _ in range(q)]
  ed=defaultdict(deque)
  wt=defaultdict(int)
  for e in edges:
    ed[e[0]].append(e[1])
    ed[e[1]].append(e[0])
    wt[(e[0],e[1])]=e[2]
    wt[(e[1],e[0])]=e[2]
  stack=deque([k])
  cv=stack[0]
  dist=defaultdict(int)
  while stack:
    while ed[cv]:
      if cv!=k:
        if ed[cv][-1]==stack[-1]:
          ed[cv].pop()
          if not ed[cv]:
            break
      stack.append(cv)
      cv=ed[cv].pop()
      dist[cv]=dist[stack[-1]]+wt[(stack[-1],cv)]
    cv=stack.pop()
  print(dist)
  for que in xy:
    print(dist[que[0]]+dist[que[1]])

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
def solve():
    import heapq
    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))
    inf = 10**10
    dist = [inf] * n

    def dijkstra(s):
        q = []
        dist[s] = 0
        heapq.heappush(q, [0, s])
        while q:
            p, v = heapq.heappop(q)
            if dist[v] < p:
                continue
            for i, x in g[v]:
                if dist[i] > dist[v] + x:
                    dist[i] = dist[v] + x
                    heapq.heappush(q, [dist[i], i])

    m, k = map(int, input().split())
    k = k - 1
    dijkstra(k)
    for _ in range(m):
        e, f = map(int, input().split())
        res = dist[e - 1] + dist[f - 1]
        print(res)


solve()

Submission status: Wrong Answer

Solution code:
def solve():
    class WeightedUnionFind:
        def __init__(self, n):
            self.par = [i for i in range(n + 1)]
            self.rank = [0] * (n + 1)
            self.weight = [0] * (n + 1)

        def root(self, x):
            if self.par[x] == x:
                return x
            else:
                y = self.root(self.par[x])
                self.weight[x] += self.weight[self.par[x]]
                self.par[x] = y
                return y

        def unite(self, x, y, w):
            rx = self.root(x)
            ry = self.root(y)
            if self.rank[rx] < self.rank[ry]:
                self.par[rx] = ry
                self.weight[rx] = w - self.weight[x] + self.weight[y]
            else:
                self.par[ry] = rx
                self.weight[ry] = -w - self.weight[y] + self.weight[x]
                if self.rank[rx] == self.rank[ry]:
                    self.rank[rx] += 1

        def same(self, x, y):
            return self.root(x) == self.root(y)

        def diff(self, x, y):
            return self.weight[x] - self.weight[y]

    n = int(input())
    wuf = WeightedUnionFind(n)
    for _ in range(n - 1):
        l, r, d = map(int, input().split())
        wuf.unite(l - 1, r - 1, d)
    m, k = map(int, input().split())
    for _ in range(m):
        res = 0
        a, b = map(int, input().split())
        res -= wuf.weight[a - 1] + wuf.weight[b - 1] + 2 * wuf.weight[k - 1]
        print(res)

solve()

Submission status: Wrong Answer

Solution code:
n = int(input())
V = [[] for i in range(n+1)]
for i in range(n-1):
    a,b,c = map(int,input().split())
    V[a].append([b,c])
    V[b].append([a,c])
tree_edge = -1
for i in range(1,n+1):
    if len(V[i]) == 1:
        tree_edge = i
        break
c_sum = [-1]*(n+1)
from collections import deque
Q = deque([])
Q.append(tree_edge)
c_sum[tree_edge] = 0
while Q:
    r = Q.popleft()
    for A,D in V[r]:
        if c_sum[A] == -1:
            Q.append(A)
            c_sum[A] = c_sum[r] + D
q,k = map(int,input().split())
x = [0]*q
for i in range(q):
    x,y = map(int,input().split())
    if min(c_sum[x],c_sum[y]) <= c_sum[k] <= max(c_sum[x],c_sum[y]):
        print(abs(c_sum[x]-c_sum[y]))
    else:
        print(abs(c_sum[x]-c_sum[y])+2*min(abs(c_sum[x]-c_sum[k]),abs(c_sum[y]-c_sum[k])))

Submission status: Wrong Answer

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

TO_K = []
TREE = []

def dfs(child, parent):
    for i_gch in TREE[child]:
        if i_gch[0] == parent and TO_K[child] == 0:
            TO_K[child] = TO_K[parent] + i_gch[1]
        else:
            dfs(i_gch[0], child)

    return


def main():
    n = int(input())
    abc = [[int(_) for _ in input().split()] for i in range(n-1)]
    q, k = map(int, input().split())
    xy = [[int(_) for _ in input().split()] for i in range(q)]

    global TO_K
    # index '0' is not used.
    TO_K = [0]*(n+1)

    global TREE
    # index '0' is not used.
    TREE = [[] for _ in range(n+1)]
    for a, b, c in abc:
        TREE[a].append([b, c])
        TREE[b].append([a, c])

    dfs(k, 0)

    for x, y in xy:
        print(TO_K[x]+TO_K[y])
    return


if __name__ == "__main__":
    main()
    sys.exit(0)

Submission status: Wrong Answer

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

TO_K = []
TREE = []
DISTANCE = []

def dfs(child, parent):
    for i_gch in TREE[child]:
        if i_gch[0] == parent:
            TO_K[child] = TO_K[parent] + i_gch[1]
        else:
            dfs(i_gch[0], child)

    return


def main():
    n = int(input())
    abc = [[int(_) for _ in input().split()] for i in range(n-1)]
    q, k = map(int, input().split())
    xy = [[int(_) for _ in input().split()] for i in range(q)]

    global TO_K
    # index '0' is not used.
    TO_K = [0]*(n+1)

    global TREE
    # index '0' is not used.
    TREE = [[] for _ in range(n+1)]
    for a, b, c in abc:
        TREE[a].append([b, c])
        TREE[b].append([a, c])

    dfs(k, 0)

    for x, y in xy:
        print(TO_K[x]+TO_K[y])
    return


if __name__ == "__main__":
    main()
    sys.exit(0)

Submission status: Wrong Answer

Solution code:
n = int(input())

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [i for i in range(n)] # parents
        self.rank = [1] * n # height of tree
        self.size = [1] * n # size[i] -> iをrootとするgroupのサイズ
        self.weight = [0] * n

    # 木の根を返す
    def find(self, x):
        if self.parents[x] == x:
            return x
        else:
            self.weight[x] += self.weight[self.parents[x]]
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    # ノードの重み
    def getWeight(self, x):
        # self.find(x) # 経路圧縮
        return self.weight[x]

    # x -> y のコスト
    def diffWeight(self, x, y):
        # return self.getWeight(y) - self.getWeight(x)
        return self.weight[x] + self.weight[y]

    # xとyの属する集合を併合する
    def union(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)
        if x == y:
            return
        if self.rank[rx] < self.rank[ry]:
            self.parents[rx] = ry
            self.size[ry] += self.size[rx]
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        else:
            self.parents[ry] = rx
            self.size[rx] += self.size[ry]
            self.weight[ry] = w - self.weight[y] + self.weight[x]
            # 木の高さが同じだった場合の処理
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

uf = UnionFind(n)
for i in range(n - 1):
    a, b, c = map(int, input().split())
    a, b, c = a - 1, b - 1, c
    uf.union(a, b, c)

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

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

print('時間計測')

from heapq import heappop, heappush
def dijkstra(E,s,n,inf=float('inf')):
    d = [inf]*n
    d[s] = 0
    q = []
    heappush(q,(0,s))
    while q:
        du,u = heappop(q)
        if d[u] < du:
            continue
        for v,dist in E[u]:
            dnew = du + dist
            if d[v] > dnew:
                d[v] = dnew
                heappush(q,(dnew,v))
    return d

N = I()
a,b,c = LIR(N-1,3)
Q,K = LI()
x,y = LIR(Q,2)

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

d = dijkstra(E,K-1,N,inf=10**9*(N-1)+1)

for i in range(Q):
    print(d[x[i]-1]+d[y[i]-1])

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

print('時間計測')

from heapq import heappop, heappush
def dijkstra(E,s,n,inf=float('inf')):
    d = [inf]*n
    d[s] = 0
    q = []
    heappush(q,(0,s))
    while q:
        du,u = heappop(q)
        if d[u] < du:
            continue
        for v,dist in E[u]:
            dnew = du + dist
            if d[v] > dnew:
                d[v] = dnew
                heappush(q,(dnew,v))
    return d

N = I()
a,b,c = LIR(N-1,3)
Q,K = LI()
x,y = LIR(Q,2)

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

d = dijkstra(E,K-1,N)

for i in range(Q):
    print(d[x[i]-1]+d[y[i]-1])

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

print('時間計測')

from heapq import heappop, heappush
def dijkstra(E,s,n):
    d = [10**9*(n-1)+1]*n
    d[s] = 0
    q = []
    heappush(q,(0,s))
    while q:
        du,u = heappop(q)
        if d[u] < du:
            continue
        for v,weight in E[u]:
            dnew = du + weight
            if d[v] > dnew:
                d[v] = dnew
                heappush(q,(dnew,v))
    return d

N = I()
a,b,c = LIR(N-1,3)
Q,K = LI()
x,y = LIR(Q,2)

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

d = dijkstra(E,K-1,N)

for i in range(Q):
    print(d[x[i]-1]+d[y[i]-1])

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

print('時間計測')

from heapq import heappop, heappush
def dijkstra(E,s,n):
    d = [10**9*(n-1)+1]*n
    d[s] = 0
    q = []
    heappush(q,(0,s))
    while q:
        du,u = heappop(q)
        if d[u] < du:
            continue
        for v,weight in E[u].items():
            dnew = du + weight
            if d[v] > dnew:
                d[v] = dnew
                heappush(q,(dnew,v))
    return d

N = I()
a,b,c = LIR(N-1,3)
Q,K = LI()
x,y = LIR(Q,2)

E = [dict() for _ in range(N)]
for i in range(N-1):
    E[a[i]-1][b[i]-1] = c[i]
    E[b[i]-1][a[i]-1] = c[i]

d = dijkstra(E,K-1,N)

for i in range(Q):
    print(d[x[i]-1]+d[y[i]-1])

Submission status: Wrong Answer

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


ans_list = []
def dijkstra(edges, num_v, start):
    dist = [float('inf')] * num_v
    dist[start] = 0
    q = []
    heapq.heappush(q, [0, start])

    while len(q) > 0:
        _, u = heapq.heappop(q)
        for edge in edges:
            if dist[edge[0]] > dist[u] + edge[1]:
                dist[edge[0]] = dist[u] + edge[1]
                heapq.heappush(q, [dist[u] + edge[1], edge[0]])
    return dist
for i in range(Q):
    x, y = map(lambda n: int(n) - 1, input().split())
    x_K = dijkstra(edges, N, x)[K]
    K_y = dijkstra(edges, N, K)[y]
    ans_list.append(x_K + K_y)

for i in ans_list:
    print(i)

Submission status: Wrong Answer

Solution code:
N = int(input())
edges = []
for i in range(N-1):
    a, b, c = map(int, input().split())
    edges.append([a-1, b-1, c])
    edges.append([b-1, a-1, c])
Q, K = map(int, input().split())
K -= 1
def bellman_ford(edges, num_v, start):
    dist = [float('inf') for _ in range(num_v)]
    dist[start] = 0

    changed = True
    while changed:
        changed = False
        for edge in edges:
            if dist[edge[1]] > dist[edge[0]] + edge[2]:
                dist[edge[1]] = dist[edge[0]] + edge[2]
                changed = True
    return dist

ans_list = []
base = bellman_ford(edges, N, 0)
for i in range(Q):
    x, y = map(lambda n: int(n) - 1, input().split())
    x_K = abs(base[K] - base[x])
    K_y = bellman_ford(edges, N, K)[y]
    ans_list.append(x_K + K_y)

for i in ans_list:
    print(i)

Submission status: Wrong Answer

Solution code:
import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from collections import deque, defaultdict, Counter
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
ABC = [LIST() for _ in range(N-1)]
Q, K = MAP()
xy = [LIST() for _ in range(Q)]

connection = [[] for _ in range(N)]

for i in range(N-1):
	connection[ABC[i][0]-1].append((ABC[i][1]-1, ABC[i][2]))
	connection[ABC[i][1]-1].append((ABC[i][0]-1, ABC[i][2]))

#print(connection)

step = [-1]*N
step[K-1] = 0

q = deque([K-1])


while q:
	N = q.popleft()
	for x, C in connection[N]:
		#print(x, C)
		if step[x] == -1:
			step[x] = step[N] + C
			#print(step)
			q.append(x)


print(step)

for x, y in xy:
	print(step[x-1] + step[y-1])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    
    from heapq import heappush, heappop
    
    # 頂点数V、直接移動先とコストを記したリストg、スタート地点rをとって、
    # rからiに行くまでの最低コストがdist[i]であることを意味するリストdistを返す関数
    def dijkstra(V, g, r):
    
        dist = [INF] * V
        queue = [(0, r)]  # queueの要素(c,v)は、コストcで直接vに行けることを意味する
        dist[r] = 0  # スタート地点rにはコスト0で行ける
    
        while queue:
            c, v = heappop(queue)
            if dist[v] < c:  # すでに記録されているコストの方が小さいので更新不要
                continue
            for cost, t in g[v]:
                if dist[v] + cost < dist[t]:
                    dist[t] = dist[v] + cost
                    heappush(queue, (dist[t], t))
    
        return dist
    N=int(input())
    V, E= N,N-1 # 頂点数、辺の数、始点
    g = [[] for i in range(V)] # 隣接リスト
    
    for i in range(E):
        s, t, d = map(int, input().split())
        g[s-1].append((d, t-1))  # g[s]の要素(cost,t)はsからコストcostでtに直接行けることを意味する
        g[t-1].append((d,s-1))
    
    INF = 10 ** 10
    
    Q,K=map(int,input().split())
    d=dijkstra(V, g, K-1)
    for i in range(Q):
        x,y=map(int,input().split())
        print(d[x-1]+d[y-1])


    
resolve()

Submission status: Wrong Answer

Solution code:

from heapq import heappush, heappop
INF = 10**10
def dijkstra(N, G, s):
    dist = [INF] * N
    que = [(0, s)]
    dist[s] = 0
    while que:
        c, v = heappop(que)
        if dist[v] < c:
            continue
        for t, cost in G[v]:
            if dist[v] + cost < dist[t]:
                dist[t] = dist[v] + cost
                heappush(que, (dist[t], t))
    return dist

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

dist = dijkstra(N,edge,K-1)

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

Submission status: Wrong Answer

Solution code:
from collections import deque

N=int(input())
g=[[] for _ in range(N)]
visit=[0]*N
dist=[0]*N
branch=[0]*N

def lac(x,y):
    yset=set()

    while True:
        y=branch[y]
        yset.add(y)
        if y==0:
            break
    
    while not (x in yset):
        x=branch[x]
    
    return x

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

    g[a].append([b,c])
    g[b].append([a,c])

q=deque([0])
visit[0]=1

while len(q)>0:
    p=q.popleft()

    cnt=0
    for c,d in g[p]:
        if visit[c]==0:
            cnt+=1
    
    for c,d in g[p]:
        if visit[c]==0:
            dist[c]=d+dist[p]
            branch[c]=branch[p] if cnt<=1 else p
            visit[c]=1
            q.append(c)
    

Q,K=list(map(int,input().split()))
K-=1

for _ in range(Q):
    x,y=list(map(int,input().split()))
    x-=1
    y-=1
    dxk=dist[x]+dist[K]-2*dist[lac(x,K)]
    dyk=dist[y]+dist[K]-2*dist[lac(y,K)]
    print(dxk+dyk)

Submission status: Wrong Answer

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

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

inf = 10**10
import heapq 
# 条件:グラフに負辺がないこと(もちろん負の閉路はない)
# V=ノード数,E=エッジ数とすると、計算量はO((V+E)logV)
# ついでに指定した始点-終点間の最短経路を求められる
def Dijkstra(ad_dict,start): # startから各頂点への最短距離を求める
    distance = [inf for _ in range(N)] # startからの距離
    previous = [inf for _ in range(N)] # previous[i]:頂点iに至る直前に居た頂点の番号．これを持っておけば，goalからstartまで戻れる
    distance[start] = 0
    heap_q = []
    heapq.heappush(heap_q, (0, start)) # (startからvへの暫定距離,v)を追加
    while heap_q:
        temp_dist, prev = heapq.heappop(heap_q)
        if distance[prev] < temp_dist:
            # startからprevまでの距離がtemp_distより小さいなら，既により最適な経路があるから，この経路は不採用
            continue
        for now, cost in ad_dict[prev].items():
            if (distance[prev] + cost) < distance[now]: # より最適なら更新
                distance[now] = distance[prev] + cost # 最短距離更新
                heapq.heappush(heap_q, (distance[now], now))
                previous[now] = prev
    return distance, previous # distance:list([int,int,...]), previous:list([int,int,...])

def reconstruct_path(distance, previous, goal): # 最短経路復元
    now = goal
    path = [goal]
    while previous[now] != inf: # now == startのときに停止
        path.append(previous[now])
        now = previous[now]
    return list(path[::-1]) # start -> goalの最短経路

D,_ = Dijkstra(G,K-1)
for i in range(Q):
    x,y = map(int,input().split())
    print(D[x-1]+D[y-1])

Submission status: Wrong Answer

Solution code:
n=int(input())
graph=[[] for i in range(n)]
for i 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())
dist=[0 for i in range(n)]




for i in range(Q):
    x,y=map(int,input().split())
    print()

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 5 + 10)


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


def resolve():
    from heapq import heappush, heappop

    # 頂点数V、直接移動先とコストを記したリストg、スタート地点rをとって、
    # rからiに行くまでの最低コストがdist[i]であることを意味するリストdistを返す関数
    def dijkstra(V, g, r):

        dist = [INF] * V
        queue = [(0, r)]  # queueの要素(c,v)は、コストcで直接vに行けることを意味する
        dist[r] = 0  # スタート地点rにはコスト0で行ける

        while queue:
            c, v = heappop(queue)
            if dist[v] < c:  # すでに記録されているコストの方が小さいので更新不要
                continue
            for cost, t in g[v]:
                if dist[v] + cost < dist[t]:
                    dist[t] = dist[v] + cost
                    heappush(queue, (dist[t], t))

        return dist

    N = int(input())
    V, E = N, N - 1  # 頂点数、辺の数、始点
    g = [[] for i in range(V)]

    for i in range(E):
        s, t, d = map(int, input().split())
        g[s - 1].append((d, t - 1))  # g[s]の要素(cost,t)はsからコストcostでtに直接行けることを意味する
        g[t - 1].append((d, s - 1))

    INF = 10 ** 10
    Q, K = map(int, input().split())
    l = dijkstra(V, g, K-1)
    for i in range(Q):
        x, y = map(int, input().split())
        print(l[x-1] + l[y - 1])


resolve()

Submission status: Wrong Answer

Solution code:
n=int(input())
INF=9999999999
d=[INF for _ in range(n)]
dist=[[INF for _ in range(n)] for _ in range(n)]
used=[False for _ in range(n)]

for i in range(n):
    dist[i][i]=0

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

def dijkstra(start):
    d[start]=0

    while(True):
        v=-1
        for u in range(n):
            if(not used[u] and (v==-1 or d[u]<d[v])):
                v=u

        if(v==-1):
            break

        used[v]=True

        for u in range(n):
            d[u]=min(d[u],d[v]+dist[v][u])

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

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

頂点Kから各ノードへの最短ルートはdfsとかで記録していけばよい。
"""
import sys
sys.setrecursionlimit(2000000)
input = sys.stdin.readline
mod = 10**9+7
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])