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 sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    # https://atcoder.jp/contests/abc070/tasks/abc070_d
    # https://atcoder.jp/contests/abc070/submissions/11681543
    from heapq import heapify, heappop, heappush
    
    N = int(input())
    inf = 10 ** 17
    
    
    def dijkstra_heap(start, edge):
        # 始点から各頂点への最短距離(頂点番号:0~N-1)
        d = [inf] * N
        used = [False] * N
        d[start] = 0
        used[start] = True
        edgelist = []
        # a:重み(//), b:次の頂点(%)
        for a, b in edge[start]:
            heappush(edgelist, a * (10 ** 6) + b)
    
        while len(edgelist):
            # まだ最短距離が決まっていない頂点の中から最小の距離のものを探す
            minedge = heappop(edgelist)
            if used[minedge % (10 ** 6)]:
                continue
            node = minedge % (10 ** 6)
            d[node] = minedge // (10 ** 6)
            used[node] = True
    
            for e in edge[node]:
                if not used[e[1]]:
                    heappush(edgelist, (e[0] + d[node]) * (10 ** 6) + e[1])
        return d
    
    
    # N:頂点数   W:辺数
    edge = [[] for i in range(N)]
    # edge[i] : iから出る道の[重み,行先]の配列
    for _ in range(N - 1):
        x, y, z = map(int, input().split())
        edge[x - 1].append((z, y - 1))
        edge[y - 1].append((z, x - 1))
    
    q, k = map(int, input().split())
    d = dijkstra_heap(k - 1, edge)
    
    for _ in range(q):
        x, y = map(int, input().split())
        print(d[x - 1] + d[y - 1])
    
resolve()

Submission status: Accepted

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

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

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

zk = dijkstra_heap(K-1)
#print(zk)

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

Submission status: Accepted

Solution code:
N = int(input())
tree = [[] for _ in range(N)]

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

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

depth = [0 for _ in range(N)]

def dfs(v, p = -1, d = 0):
    St = []
    St.append([v, p, d])
    # 空のシーケンスは偽になる
    while St:
        cur = St.pop()
        depth[cur[0]] = cur[2]
        for i, j in tree[cur[0]]:
            if i == cur[1]:
                continue
            St.append([i, cur[0], cur[2] + j])

dfs(K)

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

Submission status: Accepted

Solution code:

from heapq import heappush, heappop
INF = float("inf")
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: Accepted

Solution code:

from heapq import heappush, heappop
INF = 10**20
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: Accepted

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

graph = [[] for _ in range(N)]
for i, (ai, bi, ci) in enumerate(abc):
    graph[ai - 1].append((bi - 1, ci))
    graph[bi - 1].append((ai - 1, ci))

import heapq
MY_INF = None
    
q = [(0, K - 1)]
d = [MY_INF] * N
d[K - 1] = 0
while len(q) > 0:
    dist, src = heapq.heappop(q)
    for dst, c_dst in graph[src]:
        dist_tmp = dist + c_dst
        if d[dst] == None or d[dst] > dist_tmp:
            d[dst] = dist_tmp
            heapq.heappush(q, (dist_tmp, dst))

for i, (xi, yi) in enumerate(xy):
    print(d[xi - 1] + d[yi - 1])

Submission status: Accepted

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

n = int(input())
g = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b, c = [int(x) for x in input().split()]
    g[a - 1].append([c, b - 1])
    g[b - 1].append([c, a - 1])
q, k = [int(x) for x in input().split()]
import heapq
def dijkstra(s):
    # 始点sから各頂点への最短距離
    d = [float('inf')]*n
    d[s] = 0
    # 各頂点が訪問済みかどうか
    used = [False]*n
    used[s] = True
    # 仮の距離を記録するヒープ
    que = []
    for e in g[s]:
        heapq.heappush(que, e)
    while que:
        minedge = heapq.heappop(que)
        if used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = True
        for e in g[v]:
            if not used[e[1]]:
                heapq.heappush(que, [e[0] + d[v], e[1]])
    return d
d = dijkstra(k - 1)
for _ in range(q):
    x, y = [int(x) for x in input().split()]
    print(d[x - 1] + d[y - 1])

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

INF = 10**15

def dijkstra(s, edges):
    n = len(edges)
    que = []
    d = [INF] * n
    d[s] = 0
    heappush(que, (0, s))

    while len(que) > 0:
        (c, v) = heappop(que)
        if d[v] < c:
            continue
        for (cc, w) in edges[v]:
            if d[w] > d[v] + cc:
                d[w] = d[v] + cc
                heappush(que, (d[w], w))
    return d

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

q, k = map(int, input().split())
x, y = [], []
for i in range(q):
    xi, yi = map(int, input().split())
    xi, yi = xi-1, yi-1
    x.append(xi)
    y.append(yi)

dist = dijkstra(k-1, edge)

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

Submission status: Accepted

Solution code:
import heapq
from collections import deque
class Graph:
    def __init__(self,v,edgelist,w_v = None,directed = False):
        super().__init__()
        self.v = v
        self.w_e = [{} for _ in [0]*self.v]
        self.neighbor = [[] for _ in [0]*self.v]
        self.w_v = w_v
        self.directed = directed

        for i,j,w in edgelist:
            self.w_e[i][j] = w
            self.neighbor[i].append(j)

    def dijkstra(self,v_n):
        d = [float('inf')]*self.v
        d[v_n] = 0
        prev = [-1]*self.v

        queue = []
        for i,d_i in enumerate(d): heapq.heappush(queue,(d_i,i))
        
        while len(queue)>0:
            d_u,u = queue.pop()
            if d[u]<d_u :continue
            for v in self.neighbor[u]:
                alt = d[u]+self.w_e[u][v]
                if d[v]>alt:
                    d[v] = alt
                    prev[v] = u
                    heapq.heappush(queue,(alt,v))

        return d,prev

    def warshallFloyd(self):
        d = [[10**18]*self.v for _ in [0]*self.v]
        for i in range(self.v):
            d[i][i] = 0
            
        for i in range(self.v):
            for j in self.neighbor[i]:
                d[i][j] = self.w_e[i][j]
            
        for i in range(self.v):
            for j in self.neighbor[i]:
                d[i][j] = self.w_e[i][j]
        
        for k in range(self.v):
            for i in range(self.v):
                for j in range(self.v):
                    check = d[i][k] + d[k][j]
                    if d[i][j] > check:
                        d[i][j] = check
        return d

    def prim(self):
        gb = GraphBuilder(self.v,self.directed)

        queue = []
        for i,w in self.w_e[0].items(): heapq.heappush(queue,(w,0,i))
        rest = [True]*self.v
        rest[0] = False

        while len(queue)>0:
            w,i,j = heapq.heappop(queue)
            if rest[j]:
                gb.addEdge(i,j,w)
                rest[j] = False
                for k,w in self.w_e[j].items():
                    if rest[k]:
                        heapq.heappush(queue,(w,j,k))

        return gb

    def bfs(self,vartex = 0):
        todo = [True]*self.v
        queue = deque([vartex])
        while(len(queue)>0):
            v = queue.popleft
            todo[v] = False
            yield v
            for v_i in self.neighbor[v]:
                if todo[v_i]:
                    queue.append(v_i)

    def dfs(self,vartex = 0):
        seen = [False]*self.v
        def recdfs(v):
            seen[vartex] = True
            for next_v in self.neighbor[vartex]:
                if (seen[next_v]):continue
                recdfs(next_v)
    
        
            
class Tree():
    def __init__(self,v,e):
        pass

class GraphBuilder():
    def __init__(self,v,directed = False,edge = None, weights = None):
        self.v = v
        self.directed = directed
        self.edge = []
        self.weights = []
        if edge is not None:
            self.addEdges(edge)
        if weights is not None:
            self.addVartex(weights)

    def addEdge(self,i,j,w=1):
        if not self.directed:
            self.edge.append((j,i,w))
        self.edge.append((i,j,w))

    def addEdges(self,edgelist,weight = True):
        if weight:
            if self.directed:
                for i,j,w in edgelist:
                    self.edge.append((i,j,w))
            else:
                for i,j,w in edgelist:
                    self.edge.append((i,j,w))
                    self.edge.append((j,i,w))
        else:
            if self.directed:
                for i,j in edgelist:
                    self.edge.append((i,j,1))
            else:
                for i,j in edgelist:
                    self.edge.append((i,j,1))
                    self.edge.append((j,i,1))
    
    def addVartex(self,weights):
        if len(weights) != self.v:
            return
        self.weights.extend(weights)

    def addAdjMat(self, mat):
        for i,mat_i in enumerate(mat):
            for j,w in enumerate(mat_i):
                self.edge.append((i,j,w))

    def buildTree(self):
        pass

    def buildGraph(self):
        return Graph(self.v,self.edge,directed=self.directed)

n = int(input())
edge = []
for i in range(n-1):
  a,b,c = tuple(map(int,input().split()))
  edge.append((a-1,b-1,c))
gb = GraphBuilder(n)
gb.addEdges(edge)
g = gb.buildGraph()

q,k = tuple(map(int,input().split()))
dijk = g.dijkstra(k-1)[0]
for i in range(q):
  a,b = tuple(map(int,input().split()))
  a,b = a-1,b-1
  print(dijk[a]+dijk[b])

Submission status: Accepted

Solution code:
n=int(input())
edge=[[]for _ in range(n)]
for _ in range(n-1):
  a,b,c=map(int,input().split())
  a-=1
  b-=1
  edge[a].append((b,c))
  edge[b].append((a,c))
from heapq import heappop,heappush
def dijkstra(s,n,edge):
  inf=10**20
  ans=[inf]*n
  ans[s]=0
  root=[-1]*n
  h=[[0,s]]
  while h:
    c,v=heappop(h)
    if ans[v]<c:continue
    for u,t in edge[v]:
      if c+t<ans[u]:
        ans[u]=c+t
        root[u]=v
        heappush(h,[c+t,u])
  return ans
q,k=map(int,input().split())
xy=[list(map(int,input().split()))for _ in range(q)]
d=dijkstra(k-1,n,edge)
for x,y in xy:
  print(d[x-1]+d[y-1])

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

minDist = [10**18] * N
minDist[K] = 0
st = [(K, 0)]
while st:
    now, dist = st.pop()
    for to, c in edges[now]:
        d = dist + c
        if minDist[to] > d:
            minDist[to] = d
            st.append((to, d))

ans = []
for _ in range(Q):
    X, Y = map(lambda a: int(a) - 1, input().split())
    ans.append(minDist[X] + minDist[Y])

print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import copy
n = int(input())
graph = [[] for _ in range(n)]
for i in range(n-1):
    a,b,c = map(int,input().split())
    graph[a-1].append([c,b-1])
    graph[b-1].append([c,a-1])
q,k = map(int,input().split())
wait = [k-1]
d = [0]*n
done = [False]*n
while wait:
    nxt = []
    for i in wait:
        for l in graph[i]:
            if not done[l[1]]:
                done[l[1]] = True
                d[l[1]] = d[i] + l[0]
                nxt.append(l[1])
    wait = copy.copy(nxt)


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

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())

T = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b, c = map(int, input().split())
    T[a - 1].append((b - 1, c))
    T[b - 1].append((a - 1, c))
Q, K = map(int, input().split())

# dfs
table = [0] * N
D = deque([K - 1])
visited = set()
while D:
    v = D.pop()
    visited.add(v)
    for x, d in T[v]:
        if x not in visited:
            table[x] = table[v] + d
            D.append(x)

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

Submission status: Accepted

Solution code:
from collections import deque

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

Q, K = map(int, input().split())
K -= 1
DP = [-1] * N
DP[K] = 0
A = deque()
A.append((0,K))
while len(A) > 0:
    fatigue, now = A.pop()
    for next, cost in Edge[now]:
        if DP[next] > 0:
            continue
        else:
            DP[next] = fatigue + cost
            A.append((fatigue+cost, next))

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

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()

from collections import defaultdict, deque, Counter
from sys import exit
import heapq
import math
import copy
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)

N = getN()
dist = [[] for i in range(N + 1)]
for i in range(N - 1):
    a, b, c = getNM()
    dist[a].append([b, c])
    dist[b].append([a, c])
ignore = [-1] * (N + 1)

# Kからの最短距離をbfsで測る
def distance(sta):
    # 木をKから順にたどる（戻るの禁止）
    pos = deque([sta])

    while len(pos) > 0:
        u = pos.popleft()
        for i in dist[u]:
            if ignore[i[0]] == -1:
                ignore[i[0]] = ignore[u] + i[1]
                pos.append(i[0])

Q, K = getNM()
ignore[K] = 0
distance(K)
# 答えはK~xまでの距離+K~yまでの距離
ans = []
for i in range(Q):
    x, y = getNM()
    ans.append(ignore[x] + ignore[y])
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
#transit tree path
n=int(input())
graph={i:{} for i in range(1,n+1)}
for i in range(n-1):
    a,b,d=map(int,input().split())
    graph[a][b]=d
    graph[b][a]=d

import heapq
def dijkstra(s,graph,n):
    dist=[10**20 for i in range(n+1)]
    dist[s]=0
    pq=[]
    heapq.heapify(pq)
    heapq.heappush(pq,(0,s))
    while pq:
        x=heapq.heappop(pq)
        node,mini_dis=x[1],x[0]
        for point in graph[node].keys():
            w=graph[node][point]
            newlen=dist[node]+w
            if newlen<dist[point]:
                heapq.heappush(pq,(newlen,point))
                dist[point]=newlen
    return dist
Q,K=map(int,input().split())
P=dijkstra(K,graph,n)
for i in range(Q):
    x,y=map(int,input().split())
    print(P[x]+P[y])

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
graph = [[] 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())
visited = [0] * N
visited[K - 1] = 1
q = deque([(K - 1, 0)])
while q:
    p, c = q.popleft()
    for dst, d in graph[p]:
        if not visited[dst]:
            visited[dst] = c + d
            q.append((dst, c + d))
for _ in range(Q):
    x, y = map(lambda n: int(n) - 1, input().split())
    print(visited[x] + visited[y])

Submission status: Accepted

Solution code:
N=int(input())
import sys
sys.setrecursionlimit(10**6)
T=[[] for _ in range(N)]
for i in range(N-1):
    a,b,c=map(int, input().split())
    T[a-1].append((b-1,c))
    T[b-1].append((a-1,c))

Q,K=map(int, input().split())
D=[-1]*N
D[K-1]=0
def dfs(start, nowd):
    to=T[start]
    for t in to:
        next_node,c=t
        if D[next_node]!=-1:
            continue
        nextd=nowd+c
        D[next_node]=nextd
        dfs(next_node, nextd)
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

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

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,K=list(map(int,input().split()))
K-=1

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

while len(q)>0:
    p=q.popleft()
    
    for c,d in g[p]:
        if visit[c]==0:
            dist[c]=d+dist[p]
            visit[c]=1
            q.append(c)
    
for _ in range(Q):
    x,y=list(map(int,input().split()))
    x-=1
    y-=1
    print(dist[x]+dist[y])

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())
graph = [[] 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())

distance = [float('inf') for _ in range(n)]
distance[k - 1] = 0

d = deque()
d.append(k - 1)
visited = set({})
while d:
    point = d.popleft()
    for index, value in graph[point]:
        distance[index] = min(distance[point] + value, distance[index])
        if index not in visited:
            d.append(index)
    visited.add(point)
    
for _ in range(q):
    x, y = map(int, input().split())
    print(distance[x - 1] + distance[y - 1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)


n=int(input())

c={}
tree=[set([]) for _ in range(n)]

for _ in range(n-1):
    i,j,k=map(int,input().split())
    i-=1
    j-=1
    tree[i].add(j)
    tree[j].add(i)
    c[(min(i,j),max(i,j))]=k

result=[]
q,k=map(int,input().split())

memo=[-1]*n

def DEF(z,cnt):
    global memo,tree,c
    memo[z]=cnt
    for item in tree[z]:
        if memo[item]==-1:
            DEF(item,cnt+c[(min(item,z),max(item,z))])

DEF(k-1,0)
result=[]
for item in range(q):
    a,b=map(int,input().split())
    result.append(memo[a-1]+memo[b-1])

for item in result:
    print(item)

Submission status: Accepted

Solution code:
import sys
import heapq


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


sys.setrecursionlimit(10 ** 9)


MOD = 10 ** 9 + 7


def dijkstra(start, n_nodes, edge):
    dist = [float("inf")] * n_nodes
    dist[start] = 0
    # 優先度キューの準備
    q = [(dist[start], start)]
    heapq.heapify(q)
    while q:
        # スタートから最も最短距離のものを取り出す
        d, i = heapq.heappop(q)
        # 記録してある情報よりも，取り出した要素に入っている距離情報の方が大きければ
        # 打ち切り．次の要素を取り出す操作に戻る
        if dist[i] < d:
            continue
        # そこから移動できる頂点を探し，最短距離が更新できるものがあれば，
        # 距離を更新して，その頂点への距離と頂点の方法を優先度キューにpush
        for cost, j in edge[i]:
            if dist[j] > dist[i] + cost:
                dist[j] = dist[i] + cost
                heapq.heappush(q, (dist[j], j))
    return dist


def main():
    N = int(input())
    edge = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b, c = map(int, input().split())
        edge[a - 1].append((c, b - 1))
        edge[b - 1].append((c, a - 1))
    Q, K = map(int, input().split())
    D = dijkstra(K - 1, N, edge)
    for _ in range(Q):
        x, y = map(int, input().split())
        print(D[x - 1] + D[y - 1])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())
g = [[] for _ in range(n+1)]
for _ in range(n-1):
    a,b,c = map(int,input().split())
    g[a].append((b,c))
    g[b].append((a,c))
q,k  = map(int,input().split())
dis = [float('inf')]*(n+1)
dis[k] = 0
que = deque(g[k])
while que:
    x,y  = que.popleft()
    if dis[x] == float('inf'):
        dis[x] = y
        for x_, y_ in g[x]:
            que.append((x_, dis[x]+y_))
    else:
        dis[x] = min(dis[x], y)

ans = []
for _ in range(q):
    x,y = map(int,input().split())
    ans.append(dis[x] + dis[y])
for a in ans:
    print(a)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
n=int(input())
l=[[] for i in range(n)]
C=[0]*n
for i in range(n-1):
    a,b,c=map(int,input().split())
    a-=1
    b-=1
    l[a].append([b,c])
    l[b].append([a,c])
def dfs(now,par,cost):
    C[now]=cost
    L=l[now]
    for i in range(len(L)):
        if L[i][0]==par:
            continue
        dfs(L[i][0],now,cost+L[i][1])
Q,K=map(int,input().split())
K-=1
dfs(K,K,0)
for i in range(Q):
    x,y=map(int,input().split())
    x-=1
    y-=1
    print(C[x]+C[y])

Submission status: Accepted

Solution code:
class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK
    
    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        """ 重み付き有向辺
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点の数
        """
        self.G = [[] for i in range(V)]  # 隣接リストG[u][i] := 頂点uのi個目の隣接辺
        self._E = 0  # 辺の数
        self._V = V  # 頂点の数

    @property
    def E(self):
        """ 辺数
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return self._E
    
    @property
    def V(self):
        """ 頂点数 """
        return self._V
    
    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1
        
    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す 
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短コストを格納したリスト。
                     到達不可の場合、値はfloat("inf")
        """
        import heapq
        que = []  # プライオリティキュー（ヒープ木）
        d = [float("inf")] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  # 始点の(最短距離, 頂点番号)をヒープに追加する

        while len(que) != 0:
            cost, v = heapq.heappop(que)
            # キューに格納されている最短経路の候補がdの距離よりも大きければ、他の経路で最短経路が存在するので、処理をスキップ
            if d[v] < cost: continue

            for i in range(len(self.G[v])):
                # 頂点vに隣接する各頂点に関して、頂点vを経由した場合の距離を計算し、今までの距離(d)よりも小さければ更新する
                e = self.G[v][i]  # vのi個目の隣接辺e
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost  # dの更新
                    heapq.heappush(que, (d[e.to], e.to))  # キューに新たな最短経路の候補(最短距離, 頂点番号)の情報をpush
        return d

n = int(input())
djk = Dijkstra(n)
for i in range(n - 1):
    a, b, c = map(int, input().split())
    djk.add(a-1, b - 1, c)
    djk.add(b - 1, a - 1, c)

q, k = map(int, input().split())
d = djk.shortest_path(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
input = sys.stdin.readline
def main():
  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)]
  # 頂点kを根とした根付き木。kから各頂点への最短距離を求めてクエリごとに足すだけ。
  ki=[[]for _ in range(n)]
  for a,b,c in abc:
    ki[a-1].append([b-1,c])
    ki[b-1].append([a-1,c])
  kakutei=[0]*n
  kyori=[pow(10,14)]*n
  kyori[k-1]=0
  import heapq
  mikakutei=[[0,k-1]]
  heapq.heapify(mikakutei)
  while len(mikakutei)>0:
    k,i=heapq.heappop(mikakutei)
    if kakutei[i]==1:
      continue
    kakutei[i]=1
    l=ki[i]
    for li in l:
      if kakutei[li[0]]==0:
        kyori[li[0]]=min(kyori[li[0]],k+li[1])
        heapq.heappush(mikakutei,[kyori[li[0]],li[0]])
  for x,y in xy:
    print(kyori[x-1]+kyori[y-1])
    

if __name__=='__main__':
  main()

Submission status: Accepted

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

N = int(input())

vertex = [{} for _ in range(N)]

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

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

d = [0 for i in range(N)]

def dfs(v1,v2):
    d[v2] = d[v1] + vertex[v1][v2]
    for v in vertex[v2]:
        if v == v1:
            continue
        dfs(v2,v)

for v in vertex[K-1].keys():
    dfs(K-1,v)

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

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
from collections import deque

def main():
    N = int(readline())
    path = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b, c = map(int, readline().rstrip().split())
        path[a-1].append((b-1, c))
        path[b-1].append((a-1, c))
    Q, K = map(int, readline().rstrip().split())
    K -= 1

    dist = [-1] * N
    dist[K] = 0
    
    que = deque([K])
    while que:
        pre = que.popleft()
        for next, d in path[pre]:
            if dist[next] == -1:
                dist[next] = dist[pre] + d
                que.append(next)

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
from collections import deque

def main():
    N = int(readline())
    path = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b, c = map(int, readline().rstrip().split())
        path[a-1].append((b-1, c))
        path[b-1].append((a-1, c))
    Q, K = map(int, readline().rstrip().split())
    K -= 1

    dist = [-1] * N
    dist[K] = 0
    for n, c in path[K]:
        dist[n] = c
        
    que = deque([(K, n) for n, c in path[K]])
    while que:
        pre, now = que.popleft()
        for next, d in path[now]:
            if next != pre:
                dist[next] = dist[now] + d
                que.append((now, next))

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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**20
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
    hq = []
    heapq.heappush(hq, (0, start)) # (startからvへの暫定距離,v)を追加
    while hq:
        temp_dist, prev = heapq.heappop(hq)
        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(hq, (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])