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:
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((c,b-1))
    graph[b-1].append((c,a-1))
Q,K = map(int,input().split())

from heapq import heappush, heappop
def dijkstra(graph:list, node:int, start:int) -> list:
    # graph[node] = [(cost, to)]
    inf = float('inf')
    dist = [inf]*node

    dist[start] = 0
    heap = [(0,start)]
    while heap:
        cost,thisNode = heappop(heap)
        for NextCost,NextNode in graph[thisNode]:
            dist_cand = dist[thisNode]+NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap,(dist[NextNode],NextNode))
    return dist
    # dist = [costs to nodes]

cost = dijkstra(graph,N,K-1)
for i in range(Q):
    x,y = map(int,input().split())
    print(int(cost[x-1]+cost[y-1]))

Submission status: Accepted

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

C = [float("inf") for _ in range(N)]
V = [False for _ in range(N)]
C[K-1] = 0
H = [(0, K-1)] 
heapq.heapify(H)
while H:
    cost, node = heapq.heappop(H)
    V[node] = True
    for n in P[node]:
        if V[n[1]] == False:
            if n[0] + cost < C[n[1]]:
                C[n[1]] = n[0] + cost
                heapq.heappush(H, (n[0] + cost, n[1]))
Ans = []
for i in range(Q):
    x, y = map(int, input().split())
    Ans.append(C[x-1]+C[y-1])
for i in range(Q):
    print(Ans[i])

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from collections import deque
N = int(input())
G = [[] for i in range(N)]
for i 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

INF = float("inf")
d = [INF] * N
d[K] = 0
que = [(0, K)]
while que:
    cost, v = heappop(que)
    if d[v] < cost:
        continue
    for w, c in G[v]:
        if d[v] + c < d[w]:
            d[w] = d[v] + c
            heappush(que, (d[w], w))

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

Submission status: Accepted

Solution code:
N = int(input())
edge = [{} for _ in range(N + 1)]
dist = [-1] * (N + 1)
for _ in range(N - 1):
    a, b, c = map(int, input().split())
    edge[a][b] = c
    edge[b][a] = c

Q, K = map(int, input().split())
dist[K] = 0
dfs_stack = [K]
while dfs_stack:
    s = dfs_stack.pop()
    for t, t_dist in edge[s].items():
        if dist[t] == -1:
            dist[t] = dist[s] + t_dist
            dfs_stack.append(t)

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

Submission status: Accepted

Solution code:
N = int(input())
edge = [{} for _ in range(N + 1)]
dist = [-1] * (N + 1)
for _ in range(N - 1):
    a, b, c = map(int, input().split())
    edge[a][b] = c
    edge[b][a] = c

Q, K = map(int, input().split())
dist[K] = 0
dfs_stack = [(K, 0)]
while dfs_stack:
    s, s_dist = dfs_stack.pop()
    for t, t_dist in edge[s].items():
        if dist[t] == -1:
            dist[t] = s_dist + t_dist
            dfs_stack.append((t, dist[t]))

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

Submission status: Accepted

Solution code:
import heapq

n = int(input())
adj = [[] for _ in range(n+1)]
for _ in range(n-1):
    a, b, c = list(map(int, input().split()))
    adj[a].append((c,b))
    adj[b].append((c,a))
#print(adj)
q, k = list(map(int, input().split()))

# Djkstra
distance = [10**15]*(n+1)
distance[k] = 0
h = []
heapq.heappush(h,[0,k])
while h:
    dist, node = heapq.heappop(h)
    for ndist, nnode in adj[node]:
        if distance[nnode] > distance[node] + ndist:
            distance[nnode] = distance[node] + ndist
            heapq.heappush(h, [distance[nnode],nnode])
#print(distance)

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

Submission status: Accepted

Solution code:
import heapq

n = int(input())
g = [[] for i in range(n)]
for i in range(n-1):
    a, b, c = map(int, input().split())
    g[a-1].append((b-1, c))
    g[b-1].append((a-1, c))
q, k = map(int, input().split())
qs = [tuple(map(int, input().split())) for i in range(q)]

INF = float('inf')
dist = [INF for i in range(n)]
dist[k-1] = 0
hq = [(0, k-1)]
while hq:
    cost, node = heapq.heappop(hq)

    # heapqにすでに入った要素で、その要素よりも短い距離で更新されたものは
    # 最短距離になり得ないので候補から外す (今回は木なので関係なし)
    if cost > dist[node]:
        continue

    for n_node, n_cost in g[node]:
        d = dist[node] + n_cost
        if d < dist[n_node]:
            dist[n_node] = d
            heapq.heappush(hq, (dist[n_node], n_node))

for i in range(q):
    print(dist[qs[i][0]-1] + dist[qs[i][1]-1])

Submission status: Accepted

Solution code:
import heapq

n = int(input())
g = [[] for i in range(n)]
for i in range(n-1):
    a, b, c = map(int, input().split())
    g[a-1].append((b-1, c))
    g[b-1].append((a-1, c))
q, k = map(int, input().split())
qs = [tuple(map(int, input().split())) for i in range(q)]

INF = float('inf')
dist = [INF for i in range(n)]
dist[k-1] = 0
hq = [(0, k-1)]
while hq:
    cost, node = heapq.heappop(hq)
    if cost > dist[node]:
        continue
    for n_node, n_cost in g[node]:
        d = dist[node] + n_cost
        if d < dist[n_node]:
            dist[n_node] = d
            heapq.heappush(hq, (dist[n_node], n_node))

for i in range(q):
    print(dist[qs[i][0]-1] + dist[qs[i][1]-1])

Submission status: Accepted

Solution code:
import heapq

n = int(input())
g = [[] for i in range(n)]
for i in range(n-1):
    a, b, c = map(int, input().split())
    g[a-1].append((b-1, c))
    g[b-1].append((a-1, c))
q, k = map(int, input().split())
qs = [tuple(map(int, input().split())) for i in range(q)]

INF = float('inf')
dist = [INF for i in range(n)]
dist[k-1] = 0
hq = [(0, k-1)]
while hq:
    cost, node = heapq.heappop(hq)
    for n_node, n_cost in g[node]:
        d = dist[node] + n_cost
        if d < dist[n_node]:
            dist[n_node] = d
            heapq.heappush(hq, (dist[n_node], n_node))

for i in range(q):
    print(dist[qs[i][0]-1] + dist[qs[i][1]-1])

Submission status: Accepted

Solution code:
import heapq

n = int(input())
g = [[] for i in range(n)]
for i in range(n-1):
    a, b, c = map(int, input().split())
    g[a-1].append((b-1, c))
    g[b-1].append((a-1, c))
q, k = map(int, input().split())
qs = [tuple(map(int, input().split())) for i in range(q)]

INF = float('inf')
dist = [INF for i in range(n)]
dist[k-1] = 0
hq = [(0, k-1)]
heapq.heapify(hq)
while hq:
    cost, node = heapq.heappop(hq)
    for n_node, n_cost in g[node]:
        d = dist[node] + n_cost
        if d < dist[n_node]:
            dist[n_node] = d
            heapq.heappush(hq, (dist[n_node], n_node))

for i in range(q):
    print(dist[qs[i][0]-1] + dist[qs[i][1]-1])

Submission status: Accepted

Solution code:
import heapq

n = int(input())
g = [[] for i in range(n)]
for i in range(n-1):
    a, b, c = map(int, input().split())
    g[a-1].append((b-1, c))
    g[b-1].append((a-1, c))
q, k = map(int, input().split())
x = []
y = []
for i in range(q):
    X, Y = map(int, input().split())
    x.append(X)
    y.append(Y)

dist = [10**15 for i in range(n)]
h = []
heapq.heappush(h, (0, k-1))
while len(h) > 0:
    top = heapq.heappop(h)
    for i in g[top[1]]:
        d = top[0] + i[1]
        if dist[i[0]] > d:
            dist[i[0]] = d
            heapq.heappush(h, (d, i[0]))

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

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from heapq import heappush, heappop

def dijkstra(graph:list, node:int, start:int) -> list:
    # 未探索のノードは距離INF
    INF = float("inf")
    dist = [INF]*node
    
    # 始点ノードの距離を0とし、dfsのためのpriority queを作成
    dist[start] = 0
    heap = [(0,start)]
    
    # 未探索のノードをpriority queueに入れる
    while heap:
        cost, cur_node = heappop(heap)
        
        for nex_cost, nex_node in graph[cur_node]:
            dist_cand = dist[cur_node] + nex_cost
            if dist_cand < dist[nex_node]:
                dist[nex_node] = dist_cand
                heappush(heap, (dist[nex_node], nex_node))
    
    return dist

n = ni()
abc = []
for _ in range(n-1):
    a,b,c = li()
    a -= 1
    b -= 1
    abc.append((a,b,c))
q,k = li()
k -= 1
query = [li_() for _ in range(q)]

# 隣接リストつくる
graph = [[] for _ in range(n)]
for frm,to,cost in abc:
    graph[frm].append((cost,to))
    graph[to].append((cost,frm))

# 頂点Kをスタートとするダイクストラ
dist = dijkstra(graph, n, k)

# クエリ処理
for frm,to in query:
    print(dist[frm] + dist[to])

Submission status: Accepted

Solution code:
import heapq
N = int(input())
src = [tuple(map(int,input().split())) for i in range(N-1)]
Q,K = map(int,input().split())
K -= 1
qs = [tuple(map(int,input().split())) for i in range(Q)]

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

INF = float('inf')
dists = [INF] * N
dists[K] = 0
hq = [(0,K)]
heapq.heapify(hq)

while hq:
    dist,v = heapq.heappop(hq)
    dists[v] = dist
    for dd,to in es[v]:
        if dists[to] != INF: continue
        heapq.heappush(hq, (dist+dd, to))

for a,b in qs:
    a,b = a-1,b-1
    print(dists[a] + dists[b])

Submission status: Accepted

Solution code:
from collections import deque
def dfs(neigh,K):
    q = deque([K])
    d = [0]*N
    visited = [0]*N
    visited[K] = True
    while q:
        p = q.pop()
        for di,cost in neigh[p]:
            if visited[di]:
                continue
            d[di] = d[p]+cost
            visited[di] = True
            q.append(di)
    return d

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

Q,K = map(int,input().split())
d = dfs(neigh,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:
f_ = lambda: [int(x)-1 for x in input().split()]

n = int(input())
from collections import defaultdict
P = defaultdict(list)

for _ in range(n-1):
    a,b,c, = f_(); c += 1
    P[a].append((b,c))
    P[b].append((a,c))

q,k = f_(); q += 1
from collections import deque
que = deque([k])
dist = [None for i in range(n)]; dist[k] = 0

while que:
    p = que.popleft()
    for a,c in P[p]:
        if dist[a] is None:
            dist[a] = dist[p] + c
            que.append(a)

ans = []
for _ in range(q):
    x, y = f_()
    ans.append(dist[x]+dist[y])
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
# 入力
import sys
stdin = sys.stdin

def li(): return [int(x) for x in stdin.readline().split()]
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return [float(x) for x in stdin.readline().split()]
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(ns())
def nf(): return float(ns())


from heapq import heappush, heappop

def dijkstra(graph:list, node:int, start:int) -> list:
    # 未探索のノードは距離INF
    INF = float("inf")
    dist = [INF]*node
    
    # 始点ノードの距離を0とし、dfsのためのpriority queを作成
    dist[start] = 0
    heap = [(0,start)]
    
    # 未探索のノードをpriority queueに入れる
    while heap:
        cost, cur_node = heappop(heap)
        
        for nex_cost, nex_node in graph[cur_node]:
            dist_cand = dist[cur_node] + nex_cost
            if dist_cand < dist[nex_node]:
                dist[nex_node] = dist_cand
                heappush(heap, (dist[nex_node], nex_node))
    
    return dist

# 入力
n = ni()

# グラフ作成
graph = [[] for _ in range(n)]
for _ in range(n-1):
    a,b,c = li()
    a -= 1
    b -= 1
    graph[a].append((c,b))
    graph[b].append((c,a))
    
q,k = li()
query = []
for _ in range(q):
    x,y = li()
    x -= 1
    y -= 1
    query.append((x,y))

# Kからダイクストラ
dist_k = dijkstra(graph, n, k-1)
    

# クエリ処理
for x,y in query:
    print(dist_k[x] + dist_k[y])

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())
path = {}
for i in range(n-1):
    a, b, c = list(map(int, input().split()))
    if not a in path.keys():
        path[a] = [(b, c)]
    else:
        path[a].append((b, c))
        
    if not b in path.keys():
        path[b] = [(a, c)]
    else:
        path[b].append((a, c))
q, k = list(map(int, input().split()))
xy = [list(map(int, input().split())) for _ in range(q)]

dist = [None]*(n+1)
dist[k] = 0
que = deque([(k, 0)])
while len(que) > 0:
    node, d = que.popleft()
    dist[node] = d
    for node_next, d_next in path[node]:
        if dist[node_next] is None:
            que.append((node_next, d+d_next))
# print(dist)

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

Submission status: Accepted

Solution code:
from collections import deque
n=int(input())
l=[[] for _ in [0]*n]
for _ in [0]*(n-1):
  a,b,c=map(int,input().split())
  l[a-1].extend([(b-1,c)])
  l[b-1].extend([(a-1,c)])

q,k=map(int,input().split())
dst=[0 for _ in [0]*n]
que=deque([])
v,p,d=k-1,-1,0
que.append((v,p,d))
while que:
  v,p,d=que.pop()
  dst[v]=d
  for i,j in l[v]:
    if i==p:continue
    que.append((i,v,d+j))

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

Submission status: Accepted

Solution code:
def dfs():
  stack = [K]
  while len(stack) > 0:
    i = stack.pop()
    for k,v in E[i].items():
      if visited[k]:
        continue
      visited[k] = True
      distd[k] = distd[i] + v
      stack.append(k)

# input
N = int(input())
E = {}

for i in range(N-1):
  a, b, c = map(int, input().split())
  if a in E:
    E[a].setdefault(b,c)
  else:
    E[a] = {b:c}

  if b in E:
    E[b].setdefault(a,c)
  else:
    E[b] = {a:c}

#print(E)

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

# 1-indexedでとる
visited = [False] * (N+1)
distd = [1e15] * (N+1)

visited[K] = True
distd[K] = 0

dfs()

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

Submission status: Accepted

Solution code:
from collections import deque

def bfs(start):
    queue = deque([start])
    visited = []

    while queue:
        label = queue.pop()

        #if label not in visited:
        visited.append(label)

        for v in d[label]:
            if dist[v[0]] == float("inf"):
                dist[v[0]] = dist[label] + v[1]
                queue.appendleft(v[0])

    return

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

q, k = map(int, input().split())
dist = [float("inf") for _ in range(n)] # nは頂点数
dist[k - 1] = 0

bfs(k - 1)

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

Submission status: Accepted

Solution code:
import queue
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());K-=1
x=[0 for i in range(Q)]
y=[0 for i in range(Q)]
for i in range(Q):
    x[i],y[i]=map(int,input().split())
    x[i]-=1
    y[i]-=1
q=[]
q.append(K)
dist=[-1 for i in range(N)]
dist[K]=0
while(len(q)>0):
    r=q[-1]
    q.pop()
    for p in G[r]:
        if dist[p]!=-1:
            continue
        dist[p]=dist[r]+G[p][r]
        q.append(p)
for i in range(Q):
    print(dist[x[i]]+dist[y[i]])

Submission status: Accepted

Solution code:
import queue
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());K-=1
x=[0 for i in range(Q)]
y=[0 for i in range(Q)]
for i in range(Q):
    x[i],y[i]=map(int,input().split())
    x[i]-=1
    y[i]-=1
q=queue.Queue()
q.put(K)
dist=[-1 for i in range(N)]
dist[K]=0
while(not(q.empty())):
    r=q.get()
    for p in G[r]:
        if dist[p]!=-1:
            continue
        dist[p]=dist[r]+G[p][r]
        q.put(p)
for i in range(Q):
    print(dist[x[i]]+dist[y[i]])

Submission status: Accepted

Solution code:
n = int(input())
p = []
for i in range(n-1):
    p.append(list(map(int, input().split())))
q,k = map(int,input().split())
kue = []
for i in range(q):
    a,b=input().split()
    kue.append((int(a), int(b)))
import heapq

def shortest_path(edge,num_v,start):
    inf = float("inf")
    cost = [[] for i in range(n+1)]
    for path in edge:
      cost[path[0]].append((path[1],path[2]))
      cost[path[1]].append((path[0],path[2]))
    d = [inf for j in range(num_v)]
    q = []
    heapq.heappush(q, (0, start))
    d[start] = 0
    while len(q) != 0:
      prov_cost, src = heapq.heappop(q)
      if d[src] < prov_cost:
                continue
      for dest,weight in cost[src]:
        if weight != float('inf') and d[dest] > d[src] + weight:
          d[dest] = d[src] + weight
          heapq.heappush(q, (d[dest], dest))
    return d
kno = shortest_path(p,n+1,k)
for i in kue:
  print(kno[i[0]] + kno[i[1]])

Submission status: Accepted

Solution code:
import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(1000000)


# Debug output
def chkprint(*args):
    names = {
        id(v): k
        for k, v in inspect.currentframe().f_back.f_locals.items()
    }
    print(', '.join(
        names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args))


# Binary converter
def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]


# --------------------------------------------

dp = None
D = None
D_dfs_d = None


def dfs_d(v, pre, dist):
    global D_dfs_d

    D_dfs_d[v] = dist

    for next_v, d in D[v]:
        if next_v != pre:
            dfs_d(next_v, v, dist + d)

    return


def main():
    global D
    global D_dfs_d

    N = int(input())
    D_dfs_d = [-1] * (N + 1)
    D = [[] for _ in range(N + 1)]

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

    Q, K = li_input()

    # Kから各頂点までの長さをWFSで求める
    dfs_d(K, -1, 0)

    for i in range(Q):
        x, y = li_input()
        print(D_dfs_d[x] + D_dfs_d[y])


main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)

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

D = [0] * N
def dfs(pos, pre, dis):
    D[pos] = dis
    for (to, cost) in G[pos]:
        if to == pre:
            continue
        dfs(to, pos, dis + cost)


dfs(K - 1, -1, 0)

while Q:
    Q = Q - 1
    x, y = list(map(lambda a:int(a) - 1, input().split()))
    ans = D[x] + D[y]
    print (ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**5+100)
n = int(input())

edges = [[] for _ in xrange(n)]
distance = [-1 for _ in xrange(n)]

for _ in xrange(n-1):
	f,t,c = map(int,raw_input().split())

	f -= 1
	t -= 1

	edges[f].append((t,c))
	edges[t].append((f,c))

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

def dfs(v,c):
	if distance[v] == -1:
		distance[v] = c
		for to,cost in edges[v]:
			dfs(to,c+cost)

dfs(k,0)

for _ in xrange(q):
	x,y = map(int,raw_input().split())
	x -= 1
	y -= 1
	print distance[x] + distance[y]

Submission status: Accepted

Solution code:
from collections import deque
N = int( input())
D = dict()
Path = [ [] for _ in range(N)]
for _ in range(N-1):
    a, b, c = map( int, input().split())
    a, b = a-1, b-1
    D[1000000*a+b] = c
    D[1000000*b+a] = c
    Path[a].append(b)
    Path[b].append(a)
Q, K = map( int, input().split())
foot = [ 0 for _ in range(N)]
foot[K-1] = 1
length = [ 0 for _ in range(N)]
A = deque([])
for d in Path[K-1]:
    foot[d] = 1
    A.append(d)
    length[d] = D[1000000*d + K-1]
while len(A) != 0:
    d = A.pop()
    foot[d] = 1
    for g in Path[d]:
        if foot[g] == 0:
            length[g] = length[d] + D[1000000*d + g]
            A.append(g)
for _ in range(Q):
    x, y = map( int, input().split())
    print(length[x-1]+length[y-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

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

Q, K = [int(t) for t in input().split()]

def dfs(s):
    '''Kからの距離を計算'''
    global dist
    work = [s]
    while len(work) > 0:
        s = work.pop()
        for t, c in edge[s]:
            if dist[t] == None:
                dist[t] = dist[s] + c
                work.append(t)

dist = [None] * (N + 1)  # Kからの距離
dist[K] = 0
dfs(K)

for i in range(Q):
    x, y = [int(t) for t in input().split()]
    print(dist[x] + dist[y])

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
AtoZ = [chr(i) for i in range(65,65+26)]
atoz = [chr(i) for i in range(97,97+26)]

def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

N = int(input())

lines = defaultdict(set)
for i in range(N-1):
	a,b,c = inpl()
	a -= 1
	b -= 1
	lines[a].add((b,c))
	lines[b].add((a,c))

Q,s = inpl()
s -= 1
ss = [-1]*N
ss[s] = 0

def check(a,w):
	global ss
	for b,c in lines[a]:
		if ss[b] == -1:
			ss[b] = w + c
			check(b,w+c)

check(s,0)

for i in range(Q):
	x,y = inpl()
	print(ss[x-1]+ss[y-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, ABC, Q, K, XY):
    kd = [0] * (N+1)
    kd[K] = 0
    g = defaultdict(dict)
    for a, b, c in ABC:
        g[a][b] = c
        g[b][a] = c

    q = [K]
    while q:
        n = q.pop()
        for m, c in g[n].items():
            if m != K and kd[m] == 0:
                kd[m] = kd[n] + c
                q.append(m)

    for x, y in XY:
        print(kd[x] + kd[y])


def main():
    N = read_int()
    ABC = [read_int_n() for _ in range(N-1)]
    Q, K = read_int_n()
    XY = [read_int_n() for _ in range(Q)]

    slv(N, ABC, Q, K, XY)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
 
graph = [[] for x in range(n)]
 
for i in range(n - 1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append((b, c))
    graph[b].append((a, c))
 
q, k = map(int, input().split())
k -= 1
 
costs = [0 for x in range(n)]
que = []
que.append((k, 0))
while que:
    now, cost = que.pop()
    costs[now] = cost
    for node in graph[now]:
        if graph[node[0]] is not None:
            que.append((node[0], cost + node[1]))
    graph[now] = None
 
result = ""
for i in range(q):
    x, y = map(int, input().split())
    result += str(costs[x - 1] + costs[y - 1])
    result += "\n"
print(result)

Submission status: Accepted

Solution code:
from collections import defaultdict
from heapq import heappop, heappush

N = int(input())


class Graph(object):
    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    def __init__(self, graph, start):
        self.g = graph.graph

        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0
        self.prev = defaultdict(lambda: None)

        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        return self.dist[goal]

    def shortest_path(self, goal):
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


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

Q, K = map(int, input().split())
d = Dijkstra(g, K - 1)
for _ in range(Q):
    x, y = map(int, input().split())
    ans = d.shortest_distance(x - 1) + d.shortest_distance(y - 1)
    print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import heapq

N = int(input())
INF = float('inf')
edges = [list(map(int, input().split())) for _ in range(N-1)]
nodes = defaultdict(list)

for e in edges:
    nodes[e[0] - 1].append((e[2], e[1] - 1))
    nodes[e[1] - 1].append((e[2], e[0] - 1))


Q, K = map(int, input().split())
queries = [list(map(int, input().split())) for _ in range(Q)]

def dijkstra(x):
    que = []
    heapq.heapify(que)
    dist = [INF for _ in range(N)]
    dist[x] = 0
    heapq.heappush(que, (0, x))

    while que:
        p = heapq.heappop(que)
        v = p[1]
        if dist[v] < p[0]:
            continue
        for e in nodes[v]:
            if dist[e[1]] > dist[v] + e[0]:
                dist[e[1]] = dist[v] + e[0]
                heapq.heappush(que, (dist[e[1]], e[1]))

    return dist

distk = dijkstra(K - 1)

for q in queries:
    x, y = q[0] - 1, q[1] - 1
    print(distk[x] + distk[y])

Submission status: Accepted

Solution code:
n = int(input())

graph = [[] for x in range(n)]

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

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

costs = [0 for x in range(n)]
que = []
que.append((k, 0))
while que:
    now, cost = que.pop()
    costs[now] = cost
    for node in graph[now]:
        if graph[node[0]] is not None:
            que.append((node[0], cost + node[1]))
    graph[now] = None

result = ""
for i in range(q):
    x, y = map(int, input().split())
    result += str(costs[x - 1] + costs[y - 1])
    result += "\n"
print(result)

Submission status: Accepted

Solution code:
N = int(raw_input())
G = {}
for i in range(N):
  G[i] = {}
for i in range(N-1):
  a, b, c = map(int, raw_input().split())
  G[a-1][b-1] = G[b-1][a-1] = c
Q, K = map(int, raw_input().split())
K -= 1

d = [0]*N
p = [K]
while len(p)>0:
  v = p.pop()
  for n in G[v].keys():
    if n!=K and d[n]==0:
      d[n] = d[v]+G[v][n]
      p.append(n)

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

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())

G, W = [[] for i in range(N)], [[] for l in range(N)]
check, dist = [0 for j in range(N)], [-1 for k in range(N)]


def bfs(s):
    q = deque()
    check[s], dist[s] = 1, 0
    q.append(s)

    while len(q) != 0:
        u = q.popleft()
        for v in range(len(G[u])):
            if check[G[u][v]] == 0:
                check[G[u][v]], dist[G[u][v]] = 1, dist[u] + W[u][v]
                q.append(G[u][v])

        check[u] = 2


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

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

    bfs(k-1)

    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:
N = int(input())
T = [[] for i in range(N)]
for i in range(N - 1):
  [a, b, c] = [int(x) for x in input().split()]
  T[a-1].append((b-1, c))
  T[b-1].append((a-1, c))
[Q, K] = [int(x) for x in input().split()]
L = [[0, 0] for i in range(N)]
L[K-1] = [0, 1]
q = [K-1]
while(q):
  s = q.pop()
  for t in T[s]:
    if not L[t[0]][1]:
      L[t[0]][0] = L[s][0] + t[1]
      L[t[0]][1] = 1
      q.append(t[0])
for q in range(Q):
  [x, y] = [int(x) for x in input().split()]
  print(L[x-1][0] + L[y-1][0])