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: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from collections import defaultdict,deque
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 = defaultdict(lambda: defaultdict(int))

for a,b,c in abc:
    graph[a-1][b-1] = c
    graph[b-1][a-1] = c

def xfs(v,g):
    que = deque()
    que.append([v,0])
    while len(que) > 0:
        # i,dist = que.pop()  # 深さ優先探索        
        i,dist = que.popleft() #幅優先探索
        if i == g:
            return dist
        for n, val in graph[i].items():
            que.append([n,dist+val])
    return -1

for x,y in xy:
    print(xfs(x-1,K-1) + xfs(K-1,y-1))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from collections import defaultdict,deque
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 = defaultdict(lambda: defaultdict(int))

for a,b,c in abc:
    graph[a-1][b-1] = c
    graph[b-1][a-1] = c

def xfs(v,g):
    que = deque()
    que.append([v,0])
    while len(que) > 0:
        # i,dist = que.pop()  # 深さ優先探索        
        i,dist = que.popleft() #幅優先探索
        if i == g:
            return dist
        for n, val in graph[i].items():
            que.append([n,dist+val])
    return -1

distK = [-1 for _ in range(N)]
for i in range(N):
    distK[i] = xfs(K-1,i)

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from collections import defaultdict,deque
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 = defaultdict(lambda: defaultdict(int))

for a,b,c in abc:
    graph[a-1][b-1] = c
    graph[b-1][a-1] = c

def xfs(v,g):
    que = deque()
    que.append([v,0])
    while len(que) > 0:
        # i,dist = que.pop()  # 深さ優先探索        
        i,dist = que.popleft() #幅優先探索
        if i == g:
            return dist
        visited[i] = True
        for n, val in graph[i].items():
            if visited[n] == False:
                que.append([n,dist+val])

    return -1

for x,y in xy:
    visited = defaultdict(bool)
    d1 = xfs(x-1, K-1)
    visited = defaultdict(bool)
    d2 = xfs(K-1, y-1)
    print(d1 + d2)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from collections import defaultdict,deque
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 = defaultdict(lambda: defaultdict(int))

for a,b,c in abc:
    graph[a-1][b-1] = c
    graph[b-1][a-1] = c

def xfs(v,g):
    que = deque()
    que.append([v,0])
    while len(que) > 0:
        i,dist = que.pop()  # 深さ優先探索        
        # i = que.popleft() #幅優先探索
        if i == g:
            return dist
        visited[i] = True
        for n, val in graph[i].items():
            if visited[n] == False:
                que.append([n,dist+val])

    return -1

for x,y in xy:
    visited = defaultdict(bool)
    d1 = xfs(x-1, K-1)
    visited = defaultdict(bool)
    d2 = xfs(K-1, y-1)
    print(d1 + d2)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from collections import defaultdict,deque
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 = defaultdict(lambda: defaultdict(int))

for a,b,c in abc:
    graph[a-1][b-1] = c
    graph[b-1][a-1] = c

def xfs(v,g):
    que = deque()
    que.append([v,0])
    while len(que) > 0:
        i,dist = que.pop()  # 深さ優先探索        
        # i = que.popleft() #幅優先探索
        if i == g:
            return dist
        visited[i] = True
        for n, val in graph[i].items():
            if visited[n] == False:
                que.append([n,dist+val])

    return -1

for x,y in xy:
    visited = defaultdict(int)
    d1 = xfs(x-1, K-1)
    visited = defaultdict(int)
    d2 = xfs(K-1, y-1)
    print(d1 + d2)

Submission status: Time Limit Exceeded

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

def make_Graph(N, edges):#頂点の名前はi - 1で受け付ける
    graph = [ [] for i in range(N)]
    for edge in edges:
        a, b, c = edge
        graph[a].append((b,c))
        graph[b].append((a,c))
    return graph

def BFS(N, graph, start):
    Q = []
    V = []
    prev = [None] * N
    d = [float("inf")] * N
    Q.append(start)
    d[start] = 0
    while len(V) < N:
        a = Q.pop(0)
        V.append(a)
        for b, c in graph[a]:
            if b != prev[a]:
                Q.append(b)
                prev[b] = a
                d[b] = d[a] + c
    return d

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

Q, K =(int(i) for i in input().split())

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

Submission status: Time Limit Exceeded

Solution code:
def make_Graph(N, edges):#頂点の名前はi - 1で受け付ける
    graph = [ [] for i in range(N)]
    for edge in edges:
        a, b, c = edge
        graph[a].append((b,c))
        graph[b].append((a,c))
    return graph

def BFS(N, graph, start):
    Q = []
    V = []
    prev = [None] * N
    d = [float("inf")] * N
    Q.append(start)
    d[start] = 0
    while len(V) < N:
        a = Q.pop(0)
        V.append(a)
        for b, c in graph[a]:
            if b != prev[a]:
                Q.append(b)
                prev[b] = a
                d[b] = d[a] + c
    return d

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

Q, K =(int(i) for i in input().split())

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

Submission status: Time Limit Exceeded

Solution code:
def make_Graph(N, edges):#頂点の名前はi - 1で受け付ける
    graph = [ [] for i in range(N)]
    for edge in edges:
        a, b, c = edge
        graph[a].append((b,c))
        graph[b].append((a,c))
    return graph

def BFS(N, graph, start):
    Q = []
    V = []
    d = [float("inf")] * N
    Q.append(start)
    d[start] = 0
    while len(V) < N:
        a = Q.pop(0)
        V.append(a)
        for b, c in graph[a]:
            if not b in V:
                Q.append(b)
                d[b] = d[a] + c
    return d

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

Q, K =(int(i) for i in input().split())

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

Submission status: Time Limit Exceeded

Solution code:
def make_Graph(N, edges):#頂点の名前はi - 1で受け付ける
    graph = [ [] for i in range(N)]
    for edge in edges:
        a, b, c = edge
        graph[a].append((b,c))
        graph[b].append((a,c))
    return graph

def BFS(N, graph, start):
    Q = []
    V = []
    d = [float("inf")] * N
    Q.append(start)
    d[start] = 0
    while len(V) < N:
        a = Q.pop(0)
        V.append(a)
        for b, c in graph[a]:
            if not b in V:
                Q.append(b)
                d[b] = d[a] + c
    return d

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

graph = make_Graph(N, edges)

Q, K =(int(i) for i in input().split())

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

Submission status: Time Limit Exceeded

Solution code:
def make_Graph(N, edges):#頂点の名前はi - 1で受け付ける
    graph = {}
    for i in range(N):
        graph[i] = {}
    for edge in edges:
        a, b, c = edge
        graph[a][b] = c
        graph[b][a] = c
    return graph

def BFS(N, graph, start):
    Q = []
    V = []
    prev = {}
    d = {}
    for i in range(N):
        prev[i] = None
        d[i] = float("inf")
    Q.append(start)
    d[start] = 0
    while len(V) < N:
        a = Q.pop(0)
        V.append(a)
        for b, c in graph[a].items():
            if not b in V:
                Q.append(b)
                prev[b] = a
                d[b] = d[a] + c
    return d

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

graph = make_Graph(N, edges)

Q, K =(int(i) for i in input().split())

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

Submission status: Time Limit Exceeded

Solution code:
def make_Graph(N, edges):#頂点の名前はi - 1で受け付ける
    graph = {}
    for i in range(N):
        graph[i] = {}
        for j in range(N):
            graph[i][j] = 0
    for edge in edges:
        a, b, c = edge
        graph[a][b] = c
        graph[b][a] = c
    return graph

def BFS(N, graph, start):
    Q = []
    V = []
    prev = {}
    d = {}
    for i in range(N):
        prev[i] = None
        d[i] = float("inf")
    Q.append(start)
    d[start] = 0
    while len(V) < N:
        a = Q.pop(0)
        V.append(a)
        for b in range(N):
            if graph[a][b] and not b in V:
                Q.append(b)
                prev[b] = a
                d[b] = d[a] + graph[a][b]
    return d

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

graph = make_Graph(N, edges)

Q, K =(int(i) for i in input().split())

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

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import dijkstra
from scipy.sparse.csgraph import floyd_warshall
n=int(input())
g=[[float('inf') for i in range(n)]for j 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
cost=dijkstra(g,unweighted=False,directed=False)
for i in range(q):
    a,b=map(int,input().split())
    print(int(cost[a-1][k]+cost[k][b-1]))

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import dijkstra
from scipy.sparse.csgraph import floyd_warshall
n=int(input())
g=[[float('inf') for i in range(n)]for j in range(n)]
for i in range(n-1):
    a,b,c=map(int,input().split())
    g[a-1][b-1]=c
q,k=map(int,input().split())
k-=1
cost=dijkstra(g,unweighted=False,directed=False)
for i in range(q):
    a,b=map(int,input().split())
    print(int(cost[a-1][k]+cost[k][b-1]))

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import dijkstra
from scipy.sparse.csgraph import floyd_warshall
n=int(input())
g=[[float('inf') for i in range(n)]for j in range(n)]
for i in range(n-1):
    a,b,c=map(int,input().split())
    g[a-1][b-1]=c
q,k=map(int,input().split())
k-=1
cost=dijkstra(g,unweighted=False,directed=False)
z=[]
for i in range(q):
    a,b=map(int,input().split())
    z.append((a-1,b-1))
for i,j in z:
    print(int(cost[i][k]+cost[k][j]))

Submission status: Time Limit Exceeded

Solution code:
import copy
n = int(input())
d = []
for i in range(n - 1):#h:高さ
    d.append([int(m) for m in input().split()])
q, k = map(int, input().split())
z = []
for i in range(q):#h:高さ
    z.append([int(m) for m in input().split()])
e = []
for i in range(n):
    e.append([])
for i in d:
    e[i[0] - 1].append(i)
    e[i[1] - 1].append(i)
f = {}
for i in range(1, n + 1):
    if i != k:
        f[i] = 0
ar = []
pre = {}

for i in e[k - 1]:
    if k == i[0]:
        ar.append(i[1])
        f[i[1]] = i[2]
        pre[i[1]] = k
    else:
        ar.append(i[0])
        f[i[0]] = i[2]
        pre[i[0]] = k
while min(f.values()) == 0:
    ar2 = copy.deepcopy(ar)
    ar = []
    for j in ar2:
        for m in e[j - 1]:
                if j == m[0]:
                    if m[1] != pre[j]:
                        ar.append(m[1])
                        f[m[1]] = m[2] + f[j]
                        pre[m[1]] = j
                else:
                    if m[0] != pre[j]:
                        ar.append(m[0])
                        f[m[0]] = m[2] + f[j]
                        pre[m[0]] = j
for i in range(q):#h:高さ
    print(f[z[i][0]] + f[z[i][1]])
"""  
adj = []
for i in range(n):
    adj.append([])
for i in range(n):
    for j in range(n):
        adj[i].append(0)
#鱗屑行列
for i in range(q):
    adj[d[i][0] - 1][d[i][1] - 1] = d[i][2]
    adj[d[i][1] - 1][d[i][0] - 1] = d[i][2]"""

Submission status: Time Limit Exceeded

Solution code:
#dojkstra (prioroty queue ver.)
import queue
G=[]
#infの値に注意
inf=3*10**15
#V, E=map(int,input().strip().split(' '))
V=int(input().strip())
E=V-1

for i in range(V):
    G.append([])
for i in range(E):
    at,bt,ct=map(int,input().strip().split(' '))
    G[at-1].append([ct,bt-1])
    G[bt-1].append([ct,at-1]) #無向グラフのときはon
'''
#入力が0-indexedのとき
    G[at].append([ct,bt])
    G[bt].append([ct,at]) #無向グラフのときはon
'''
#入力が1-indexedのとき


def dijkstra(s):
    d=[inf]*V
    d[s]=0
    q=queue.PriorityQueue()
    q.put([0,s])
    while q.empty()==False:
        dq,v=q.get()
        if d[v]<dq:
            continue
        for i in range(len(G[v])):
            ec, et=G[v][i]
            #print(ec,et)
            if d[et]>d[v]+ec:
                d[et]=d[v]+ec
                q.put([d[et],et])
    return d

Q, K=map(int,input().strip().split(' '))
K-=1 #0-indexedに直す
x=[]
y=[]

d=dijkstra(K)

for i in range(Q):
    xt, yt=map(int,input().strip().split(' '))
    x.append(xt-1)#0-indexedに直して入れる
    y.append(yt-1)#0-indexedに直して入れる
for i in range(Q):
    print(d[x[i]]+d[y[i]])

Submission status: Time Limit Exceeded

Solution code:
#dojkstra (prioroty queue ver.)
import queue
G=[]
inf=3*10**15
#V, E=map(int,input().strip().split(' '))
V=int(input().strip())
E=V-1

for i in range(V):
    G.append([])
for i in range(E):
    at,bt,ct=map(int,input().strip().split(' '))
    G[at-1].append([ct,bt-1])
    G[bt-1].append([ct,at-1]) #無向グラフのときはon
'''
#入力が0-indexedのとき
    G[at].append([ct,bt])
    G[bt].append([ct,at]) #無向グラフのときはon
'''
#入力が1-indexedのとき


def dijkstra(s):
    d=[inf]*V
    d[s]=0
    q=queue.PriorityQueue()
    q.put([0,s])
    while q.empty()==False:
        dq,v=q.get()
        if d[v]<dq:
            continue
        for i in range(len(G[v])):
            ec, et=G[v][i]
            #print(ec,et)
            if d[et]>d[v]+ec:
                d[et]=d[v]+ec
                q.put([d[et],et])
    return d

d=[]

for i in range(V):
    d.append(dijkstra(i))

Q, K=map(int,input().strip().split(' '))
K-=1 #0-indexedに直す
x=[]
y=[]
for i in range(Q):
    xt, yt=map(int,input().strip().split(' '))
    x.append(xt-1)#0-indexedに直して入れる
    y.append(yt-1)#0-indexedに直して入れる
for i in range(Q):
    print(d[x[i]][K]+d[K][y[i]])

Submission status: Time Limit Exceeded

Solution code:
import queue
import copy
def dfs(L,start,end):
    stack = [start]
 
    visited = [start]
 
    path =[ 0 for i in range((len(L)))]
 
    while stack:
        node = stack.pop()
        for n in L[node]:
            if n[0] not in visited:
 
                path[n[0]] = path[node]  + n[1]
 
                stack.append(n[0])
                visited.append(n[0])
 
    return path
 
N = int(input())
p = []
for i in range(N-1):
    l = list(map(int,input().split()))
    p.append(l)

Q,K = map(int,input().split())
xy = []
for i in range(Q):
    xy.append(list(map(int,input().split())))
 
L = [ [] for i in range(N+1)]
for l in p:
    L[l[0]].append([l[1],l[2]])
    L[l[1]].append([l[0],l[2]])
 
d = dfs(L,K,0)
 
for i in range(Q):
    print(d[xy[i][0]]+ d[xy[i][1]])

Submission status: Time Limit Exceeded

Solution code:
import sys
def dfs(L,start):
    stack = [start]

    path =[-1]*len(L)
    path[start] = 0
    while stack:
        node = stack.pop()
        for n in L[node]:
            if path[n[0]] < 0:
                path[n[0]] = path[node]  + n[1]
                stack.append(n[0])

    return path

#input
input = sys.stdin.readline
N = int(input())
p = []
node = []
for i in range(N-1):
    l = list(map(int,input().split()))
    p.append(l)
    if l[0] not in node:
        node.append(l[0])
    if l[1] not in node:
        node.append(l[1])

Q,K = map(int,input().split())
xy = []
for i in range(Q):
    xy.append(list(map(int,input().split())))

#neigher list
L = [ [] for i in range(N+1)]
for l in p:
    L[l[0]].append([l[1],l[2]])
    L[l[1]].append([l[0],l[2]])

d = dfs(L,K)

for i in range(Q):
    print(d[xy[i][0]]+ d[xy[i][1]])

Submission status: Time Limit Exceeded

Solution code:
def dfs(L,start):
    stack = [start]

    path =[-1]*len(L)
    path[start] = 0
    while stack:
        node = stack.pop()
        for n in L[node]:
            if path[n[0]] < 0:
                path[n[0]] = path[node]  + n[1]
                stack.append(n[0])

    return path

#input
N = int(input())
p = []
node = []
for i in range(N-1):
    l = list(map(int,input().split()))
    p.append(l)
    if l[0] not in node:
        node.append(l[0])
    if l[1] not in node:
        node.append(l[1])

Q,K = map(int,input().split())
xy = []
for i in range(Q):
    xy.append(list(map(int,input().split())))

#neigher list
L = [ [] for i in range(N+1)]
for l in p:
    L[l[0]].append([l[1],l[2]])
    L[l[1]].append([l[0],l[2]])

d = dfs(L,K)

for i in range(Q):
    print(d[xy[i][0]]+ d[xy[i][1]])

Submission status: Time Limit Exceeded

Solution code:
import queue
import copy
def dfs(L,start,end):
    stack = [start]

    visited = [start]

    path =[ 0 for i in range((len(L)))]

    while stack:
        node = stack.pop()
        for n in L[node]:
            if n[0] not in visited:

                path[n[0]] = path[node]  + n[1]

                stack.append(n[0])
                visited.append(n[0])

    return path

N = int(input())
p = []
node = []
for i in range(N-1):
    l = list(map(int,input().split()))
    p.append(l)
    if l[0] not in node:
        node.append(l[0])
    if l[1] not in node:
        node.append(l[1])

Q,K = map(int,input().split())
xy = []
for i in range(Q):
    xy.append(list(map(int,input().split())))

L = [ [] for i in range(N+1)]
for l in p:
    L[l[0]].append([l[1],l[2]])
    L[l[1]].append([l[0],l[2]])

d = dfs(L,K,0)

for i in range(Q):
    print(d[xy[i][0]]+ d[xy[i][1]])

Submission status: Time Limit Exceeded

Solution code:
import queue
import copy
def dfs(L,start,end):
    stack = [start]

    visited = []

    path =[ 0 for i in range((len(L)+1))]

    while stack:
        node = stack.pop()
        if node == end:
            return path[end]
        for n in L[node]:
            if n[0] not in visited:

                path[n[0]] = path[node]  + n[1]

                stack.append(n[0])
                visited.append(n[0])


def bfs(L,start,end):
    que = queue.Queue()
    que.put(start)

    visited = [start]
    while not que.empty():
        q = que.get()
        if q == end:
            return visited

        for v in L[q]:
            if v[0] not in visited:
                visited.append(v[0])
                que.put(v[0])



N = int(input())
p = []
for i in range(N-1):
    l = list(map(int,input().split()))
    p.append(l)

Q,K = map(int,input().split())
xy = []
for i in range(Q):
    xy.append(list(map(int,input().split())))


L = [ [] for i in range(N+1)]
for l in p:
    L[l[0]].append([l[1],l[2]])
    L[l[1]].append([l[0],l[2]])

for i in range(Q):
    v1 = dfs(L,xy[i][0],K)
    v2 = dfs(L,K,xy[i][1])
    print(v1+v2)

Submission status: Time Limit Exceeded

Solution code:
import queue
import copy
def dfs(L,start,end):
    stack = [start]

    visited = []

    #path[node] : shortest path of node from start to
    path =[ 0 for i in range((len(L)+1))]

    while stack:
        node = stack.pop()
        if node == end:
            return path[end]
        for n in L[node]:
            if n[0] not in visited:

                path[n[0]] = path[node]  + n[1]

                stack.append(n[0])
                visited.append(n[0])


N = int(input())
p = []
for i in range(N-1):
    l = list(map(int,input().split()))
    p.append(l)

Q,K = map(int,input().split())
xy = []
for i in range(Q):
    xy.append(list(map(int,input().split())))


L = [ [] for i in range(N+1)]
for l in p:
    L[l[0]].append([l[1],l[2]])
    L[l[1]].append([l[0],l[2]])

pp = []
for i in range(len(p)):
    pp.append([p[i][1],p[i][0],p[i][2]])
p.extend(pp)
for i in range(Q):
    v1 = dfs(L,xy[i][0],K)
    v2 = dfs(L,K,xy[i][1])
    print(v1+v2)

Submission status: Time Limit Exceeded

Solution code:
import queue
import copy
def dfs(L,start,end):
    stack = []
    stack.append(start)

    visited = []
    path =[ [] for i in range((len(L)+1))]
    path[start].append(start)

    while stack:
        node = stack.pop()
        if node == end:
            return path[end]
        for n in L[node]:
            if n[0] not in visited:
                a = copy.deepcopy(path[node])
                a.append(n[0])
                for val in a:
                    path[n[0]].append(val)
                stack.append(n[0])
                visited.append(n[0])

N = int(input())
p = []
for i in range(N-1):
    l = list(map(int,input().split()))
    p.append(l)

Q,K = map(int,input().split())
xy = []
for i in range(Q):
    xy.append(list(map(int,input().split())))


L = [ [] for i in range(N+1)]
for l in p:
    L[l[0]].append([l[1],l[2]])
    L[l[1]].append([l[0],l[2]])

pp = []
for i in range(len(p)):
    pp.append([p[i][1],p[i][0],p[i][2]])
p.extend(pp)
for i in range(Q):
    v1 = dfs(L,xy[i][0],K)
    v2 = dfs(L,K,xy[i][1])
    v1.extend(v2[1:])
    cost = 0
    for j in range(len(v1)-1):
        for k in range(len(p)):
            if p[k][0] == v1[j] and p[k][1] == v1[j+1]:
                cost += p[k][2]
    print(cost)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
INF = 10 ** 9
ab = [ [INF for _ in range(n)] for _ in range(n) ]
p = [[] for _ in range(n)]
for _ in range(n-1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    ab[a][b] = c
    ab[b][a] = c
    p[a].append(b)
    p[b].append(a)

q, k = map(int, input().split())
xy = [tuple(int(x) - 1 for x in input().split()) for _ in range(q)]

k -= 1

d = [INF for _ in range(n)]
d[k] = 0
temp = [k]
while 1:
    next = []
    for x in temp:
        for y in p[x]:
            d[y] = d[x] + ab[x][y]
            next.append(y)
            p[y].remove(x)
    if len(next) == 0:
        break
    temp = [] + next

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
INF = 10 ** 9
ab = [ [INF for _ in range(n)] for _ in range(n) ]
p = [[] for _ in range(n)]
for _ in range(n-1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    ab[a][b] = c
    ab[b][a] = c
    p[a].append(b)
    p[b].append(a)

q, k = map(int, input().split())
xy = [tuple(int(x) - 1 for x in input().split()) for _ in range(q)]

k -= 1

d = [INF for _ in range(n)]
d[k] = 0
temp = [k]
while 1:
    next = []
    for x in temp:
        for y in p[x]:
            d[y] = d[x] + ab[x][y]
            next.append(y)
            p[y].remove(x)
    next = list(set(next))
    if len(next) == 0:
        break
    before = [] + temp
    temp = [] + next

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
INF = 10 ** 9
ab = [ [INF for _ in range(n)] for _ in range(n) ]
p = [[] for _ in range(n)]
for _ in range(n-1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    ab[a][b] = c
    ab[b][a] = c
    p[a].append(b)
    p[b].append(a)

q, k = map(int, input().split())
xy = [tuple(int(x) - 1 for x in input().split()) for _ in range(q)]

k -= 1

d = [INF for _ in range(n)]
d[k] = 0
temp = [k]
before = []
while 1:
    next = []
    for x in temp:
        for y in p[x]:
            if y not in before:
                d[y] = d[x] + ab[x][y]
                next.append(y)
    next = list(set(next))
    if len(next) == 0:
        break
    before = [] + temp
    temp = [] + next

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
def inpl(): return [int(i) for i in input().split()]

path = defaultdict(lambda: [])
N = int(input())
for _ in range(N-1):
    a, b, c = inpl()
    path[a].append((b,c))
    path[b].append((a,c))

Q, K = inpl()
now = {K}
dist = [0 for _ in range(N+1)]
visited = [False for _ in range(N+1)]
visited[K] = visited[0] = True
while True:
    for na in now.copy():
        na = now.pop()
        for nb, nc in path[na]:
            dist[nb] = dist[na] + nc
            visited[nb] = True
            path[nb].remove((na,nc))
            now.add(nb)
    if all(visited):
        break
for i in range(Q):
    x, y = inpl()
    print(dist[x]+dist[y])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
def inpl(): return [int(i) for i in input().split()]

path = defaultdict(lambda: [])
N = int(input())
for _ in range(N-1):
    a, b, c = inpl()
    path[a].append((b,c))
    path[b].append((a,c))

Q, K = inpl()
now = {K}
dist = [0 for _ in range(N+1)]
visited = [False for _ in range(N+1)]
visited[K] = visited[0] = True
while True:
    for na in now.copy():
        na = now.pop()
        for nb, nc in path[na]:
            if visited[nb]:
                continue
            dist[nb] = dist[na] + nc
            visited[nb] = True
            now.add(nb)
    if all(visited):
        break
for i in range(Q):
    x, y = inpl()
    print(dist[x]+dist[y])

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import dijkstra
import numpy as np

N = int(input())
edge = [[np.inf for i in range(N)] for i in range(N)]
for i in range(N-1):
    a,b,c = map(int,input().split())
    edge[a-1][b-1] = c
    edge[b-1][a-1] = c
Q,K = map(int,input().split())
cost = dijkstra(edge,False,K-1)
for i in range(Q):
    x,y = map(int,input().split())
    print(int(cost[x-1]+cost[y-1]))

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import dijkstra
import numpy as np

N = int(input())
edge = [[np.inf for i in range(N+1)] for i in range(N+1)]
for i 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())
cost = dijkstra(edge,indices=K)
for i in range(Q):
    x,y = map(int,input().split())
    print(int(cost[x]+cost[y]))

Submission status: Time Limit Exceeded

Solution code:
def ABC070D():
    N = int(input())
    abc = [list(map(int, input().split())) for i in range(N - 1)]
    ab = [[10000000000000 for i in range(N)] for j in range(N)]
    Q, K = map(int, input().split())
    xy = [list(map(int, input().split())) for i in range(Q)]
    for i, j, k in abc:
        ab[i - 1][j - 1] = k
        ab[j - 1][i - 1] = k

    for k in range(N):
        for i in range(N):
            for j in range(N):
                ab[i][j] = min(ab[i][j], ab[i][k] + ab[k][j])

    for x, y in xy:
        print(ab[x - 1][K - 1] + ab[K - 1][y - 1])
ABC070D()

Submission status: Time Limit Exceeded

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
for i in range(N):
    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: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

N = int(input())
neigh = [[0 for i in range(N)] for i in range(N)]
for i in range(N-1):
    a,b,c = map(int,input().split())
    neigh[a-1][b-1] = c
    neigh[b-1][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])