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 -*-
"""
http://abc070.contest.atcoder.jp/tasks/abc070_d
"""
# TLEするので、ダイクストラのアルゴリズムからの高速化が必要。
# 隣接行列をやめて隣接リストにしたところ、だいぶ速度が改善された。しかし、今度はWAが出るようになった。

from enum import Enum
from heapq import heappush, heappop


class Sssp(object):
    """ single source shortest path """
    class Status(Enum):
        """ ノードの訪問状態 """
        white = 1  # 未訪問
        gray = 2  # 訪問中
        black = 3  #訪問済

    def __init__(self, N, data):
        num_of_nodes = N+1
        self.color = [Sssp.Status.white] * num_of_nodes  # 各ノードの訪問状態
        self.d = [float('inf')] * num_of_nodes  # 始点からの重み
        self.adj = [[] for _ in range(num_of_nodes)]
        self.make_adj(data)

    def make_adj(self, data):
        # 隣接リストの作成 (接続先 コスト)のタプル
        for f, t, c in data:
            self.adj[f].insert(0, (t, c))
            self.adj[t].insert(0, (f, c))

    def dijkstra(self, start):
        self.d[start] = 0
        pq = [(0, start)]
        #heappush(pq, (0, start))

        while pq:
            cost, u = heappop(pq)
            self.color[u] = Sssp.Status.black
            if self.d[u] < cost:
                continue

            for v, c in self.adj[u]:
                if self.color[v] == Sssp.Status.black:
                    continue
                if self.d[v] > self.d[u] + c:
                    self.d[v] = self.d[u] + c
                    heappush(pq, (self.d[v], v))
                    self.color[v] = Sssp.Status.gray


def main():
    # データの入力
    N = int(input())
    data = []
    for i in range(N-1):
        data.append(list(map(int, input().split(' '))))
    queries = []
    Q, K = [int(x) for x in input().split(' ')]
    for i in range(Q):
        queries.append([int(x) for x in input().split(' ')])

    # 経路の探索
    s = Sssp(N, data)
    s.dijkstra(K)

    # 結果の表示
    for q in queries:
        print(s.d[q[0]] + s.d[q[1]])



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from scipy.sparse import*
f=lambda*z:map(int,sys.stdin.readline().split())
n,=f();a,b,c=zip(*map(f,xrange(~-n)));q,k=f();r=[0]*q
z=map(int,csgraph.dijkstra(csr_matrix((c,(a,b)),[n+1]*2),0,k)[1:])
for _ in range(q):x,y=f();r[_]=str(z[x-1]+z[y-1])
sys.stdout.write('\n'.join(r))

Submission status: Time Limit Exceeded

Solution code:
import sys
from scipy.sparse import*
f=lambda*z:map(int,sys.stdin.readline().split())
n,=f();a,b,c=zip(*map(f,[0]*~-n));q,k=f();r=[0]*q
z=map(int,csgraph.dijkstra(csr_matrix((c,(a,b)),[n+1]*2),0,k)[1:])
for _ in range(q):x,y=f();r[_]=z[x-1]+z[y-1]
sys.stdout.write('\n'.join(map(str,r)))

Submission status: Time Limit Exceeded

Solution code:
import sys
from scipy.sparse import*
f=lambda*z:map(int,sys.stdin.readline().split())
n,=f();a,b,c=zip(*map(f,[0]*~-n));q,k=f();r=[0]*q
z=csgraph.dijkstra(csr_matrix((c,(a,b)),[n+1]*2),0,k)
for _ in range(q):x,y=f();r[_]=int(z[x]+z[y])
sys.stdout.write('\n'.join(map(str,r)))

Submission status: Time Limit Exceeded

Solution code:
import sys
import Queue

q = Queue.Queue()
graph = {}

def solve(x, y):
    q.put((x, 0, []))
    while not q.empty():
        start, dist, path = q.get()
        for neighbor, next_dist in graph[start]:
            if neighbor == y:
                return dist + next_dist
            if neighbor in path:
                continue
            # put the neighbor to queue
            q.put((neighbor, dist + next_dist, path + [start]))

def get_all(K, N):
    answer = {}
    stack = []
    stack.append((K, 0, []))
    while len(answer) < N:
        start, start_dist, path  = stack.pop()
        answer[start] = start_dist
        for target, target_dist in graph[start]:
            if target in path:
                continue
            stack.append((target, start_dist + target_dist, path + [start]))
    return answer

test =False
if test:
    N =3
    graph[1] = [(2, 1)]
    graph[2] = [(1, 1), (3, 1)]
    graph[3] = [(2, 1)]
    answer = get_all(2, 3)
else:
    N = int(raw_input())
    for _ in range(N - 1):
        a, b, c = raw_input().split()
        a = int(a)
        b = int(b)
        c = int(c)
        if a not in graph:
            graph[a] = [(b, c)]
        else:
            graph[a].append((b, c))
        if b not in graph:
            graph[b] = [(a, c)]
        else:
            graph[b].append((a, c))

    Q, K = raw_input().split()
    Q = int(Q)
    K = int(K)
    answer = get_all(K, N)
    for _ in range(Q):
        x, y = raw_input().split()
        x = int(x)
        y = int(y)
        print answer[x] + answer[y]

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
http://abc070.contest.atcoder.jp/tasks/abc070_d
"""


from enum import Enum


class Sssp(object):
    """ single source shortest path """
    INFINITY = 999999999999
    class Status(Enum):
        """ ノードの訪問状態 """
        white = 1  # 未訪問
        gray = 2  # 訪問中
        black = 3  #訪問済

    def __init__(self, N, data):
        num_of_nodes = N+1
        self.color = [Sssp.Status.white] * num_of_nodes  # 各ノードの訪問状態
        self.M = [[Sssp.INFINITY] * num_of_nodes for _ in range(num_of_nodes)]
        self._make_matrix(data)  # dataから作成した隣接行列(未接続部分はコスト無限大に変換済)
        self.d = [Sssp.INFINITY] * num_of_nodes  # 始点からの重み
        self.p = [-1] * num_of_nodes  # 各頂点の親の番号を記録するための配列

    def _make_matrix(self, data):
        """ 重み付き有効グラフの隣接行列を作成する
        入力データは先頭2つが自ノード番号と出次数、以降は出次数の分だけ(接続先ID, 重み)のペアが続く
        """
        for my_id, to_id, cost in data:
            self.M[my_id][to_id] = cost
            self.M[to_id][my_id] = cost


    def dijkstra(self, start):
        self.d[start] = 0
        self.p[start] = -1

        while True:
            mincost = Sssp.INFINITY
            # 以降の処理で親ノードとして働くノードuを選択する
            for i in range(len(self.d)):
                if self.color[i] != Sssp.Status.black and self.d[i] < mincost:  # Sに属しておらず、Sと接続があるノードのうち重みが最小のものを選択
                    mincost = self.d[i]
                    u = i  # uが親ノードのID

            if mincost == Sssp.INFINITY:
                break

            self.color[u] = Sssp.Status.black  # ノードuはSに属している側に

            for v in range(len(self.d)):
                if self.color[v] != Sssp.Status.black and self.M[u][v] != Sssp.INFINITY:
                    # vへの重みを考えた時、新たにSに加わったuからの経路の方が重みが低ければ、その情報で更新する
                    if self.d[u] + self.M[u][v] < self.d[v]:
                        self.d[v] = self.d[u] + self.M[u][v]
                        self.p[v] = u
                        self.color[v] = Sssp.Status.gray


def main():
    # データの入力
    N = int(input())
    data = []
    for i in range(N-1):
        data.append(list(map(int, input().split(' '))))
    queries = []
    Q, K = [int(x) for x in input().split(' ')]
    for i in range(Q):
        queries.append([int(x) for x in input().split(' ')])

    # 経路の探索
    s = Sssp(N, data)
    s.dijkstra(K)

    # 結果の表示
    for q in queries:
        print(s.d[q[0]] + s.d[q[1]])



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
edge = set(tuple(map(int, input().split())) for i in range(N-1))
Q, K = map(int, input().split())
query = [tuple(map(int, input().split())) for i in range(Q)]

# dist[-i]:頂点Kから頂点iまでの距離
dist = [None for i in range(N)]
dist[-K] = 0
while edge:
    rm = set()
    for a, b, c in edge:
        if dist[-a] is not None:
            dist[-b] = dist[-a] + c
            rm.add((a, b, c))
        elif dist[-b] is not None:
            dist[-a] = dist[-b] + c
            rm.add((a, b, c))
    edge -= rm

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
abc = [[int(n) for n in input().split()] for i in range(N-1)]	
a,b,c = list(zip(*abc))
Q,K = map(int,input().split())
xy = [[int(l) for l in input().split()] for m in range(Q)]
x,y = list(zip(*xy))

l_rin = [[] for o in range(N)]
for m in range(N-1):
	l_rin[a[m]-1].extend([b[m]])
	l_rin[b[m]-1].extend([a[m]])

def search(top,bottom):
	keiro =[[top]]
	while len(keiro) > 0:
		path = keiro.pop(0)
		r = path[len(path)-1]		
		if r == bottom:
			return path
			break
		else:
			for p in l_rin[r-1]:
				if p not in path:
					new_path = path[:]
					new_path.append(p)
					keiro.append(new_path)

def distance(fst,scd):
	dist = 0
	ppath = search(fst,scd)
	for pv in range(len(ppath) - 1):
		ppath_set = set(ppath[pv:pv+2])
		for pn in range(N-1):
			ab_set = set([a[pn],b[pn]])
			if ab_set == ppath_set:
				dist = dist + c[pn]
				break
	return dist

dis_K_xy ={}
flat_list = list(set([fl for inner_list in l_rin for fl in inner_list]))
flat_list.remove(K)
flat_list.sort()
for flp in flat_list:
	dis_K_xy[flp] = distance(K,flp)

for s in range(Q):
	print(dis_K_xy[x[s]] + dis_K_xy[y[s]])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
abc = [[int(n) for n in input().split()] for i in range(N-1)]	
a,b,c = list(zip(*abc))
Q,K = map(int,input().split())
xy = [[int(l) for l in input().split()] for m in range(Q)]
x,y = list(zip(*xy))

l_rin = [[] for o in range(N)]
for m in range(N-1):
	l_rin[a[m]-1].extend([b[m]])
	l_rin[b[m]-1].extend([a[m]])

def search(top,bottom):
	keiro =[[top]]
	while len(keiro) > 0:
		path = keiro.pop(0)
		r = path[len(path)-1]		
		if r == bottom:
			return path
			break
		else:
			for p in l_rin[r-1]:
				if p not in path:
					new_path = path[:]
					new_path.append(p)
					keiro.append(new_path)

def distance(fst,scd):
	dist = 0
	ppath = search(fst,scd)
	for pv in range(len(ppath) - 1):
		ppath_set = set(ppath[pv:pv+2])
		for pn in range(N-1):
			ab_set = set([a[pn],b[pn]])
			if ab_set == ppath_set:
				dist = dist + c[pn]
				break
	return dist
			
for s in range(Q):
	print(distance(x[s],K) + distance(K,y[s]))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
abc = [[int(n) for n in input().split()] for i in range(N-1)]	
a,b,c = list(zip(*abc))
Q,K = map(int,input().split())
xy = [[int(l) for l in input().split()] for m in range(Q)]
x,y = list(zip(*xy))

l_rin = [[] for o in range(N)]
for m in range(N-1):
	l_rin[a[m]-1].extend([b[m]])
	l_rin[b[m]-1].extend([a[m]])

def search(top,bottom):
	keiro =[[top]]
	while len(keiro) > 0:
		path = keiro.pop(0)
		r = path[len(path)-1]		
		if r == bottom:
			return path
		else:
			for p in l_rin[r-1]:
				if p not in path:
					new_path = path[:]
					new_path.append(p)
					keiro.append(new_path)

def distance(fst,scd):
	dist = 0
	ppath = search(fst,scd)
	for pv in range(len(ppath) - 1):
		ppath_set = set(ppath[pv:pv+2])
		for pn in range(N-1):
			ab_set = set([a[pn],b[pn]])
			if ab_set == ppath_set:
				dist = dist + c[pn]
				break
	return dist
			
for s in range(Q):
	print(distance(x[s],K) + distance(K,y[s]))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
abc = [[int(n) for n in input().split()] for i in range(N-1)]	
a,b,c = list(zip(*abc))
Q,K = map(int,input().split())
xy = [[int(l) for l in input().split()] for m in range(Q)]
x,y = list(zip(*xy))

l_rin = [[] for o in range(N)]
for m in range(N-1):
	l_rin[a[m]-1].extend([b[m]])
	l_rin[b[m]-1].extend([a[m]])

def search(top,bottom):
	keiro =[[top]]
	while len(keiro) > 0:
		path = keiro.pop(0)
		r = path[len(path)-1]		
		if r == bottom:
			return path
		else:
			for p in l_rin[r-1]:
				if p not in path:
					new_path = path[:]
					new_path.append(p)
					keiro.append(new_path)

def distance(fst,scd):
	dist = 0
	ppath = search(fst,scd)
	for pv in range(len(ppath) - 1):
		ppath_set = set(ppath[pv:pv+2])
		for pn in range(N-1):
			ab_set = set([a[pn],b[pn]])
			if ab_set == ppath_set:
				dist = dist + c[pn]
	return dist
			
for s in range(Q):
	print(distance(x[s],K) + distance(K,y[s]))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
M = [[0 for col in range(N)] for row in range(N)]

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

Qn, K = list(map(int, input().split(" ")))

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

distance = [0]*N

def dfs(k, graph, dist):
    result = {}
    for n in range(N):
        x = graph[k][n]
        if x != 0:
            distance[n] = dist + x
            graph[n][k] = 0
            dfs(n, graph, dist + x)

dfs(K-1, M, 0)

for q in Q:
    print(distance[q[0]-1] + distance[q[1]-1])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
M = [[0 for col in range(N)] for row in range(N)]

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

Qn, K = list(map(int, input().split(" ")))

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

def dfs(k, graph, dist):
    result = {}
    for n in range(N):
        x = graph[k][n]
        if x != 0:
            result[n] = dist + x
            graph[n][k] = 0
            result.update(dfs(n, graph, dist + x))
    return result

result = dfs(K-1, M, 0)

for q in Q:
    print(result[q[0]-1] + result[q[1]-1])

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
input = stdin.readline
def BFS(K,path,N):
  """リストのリスト道順path,頂点の個数Nが与えられたとき, 頂点Kから各頂点までの距離をlistで返す"""
  dist=[-1]*N
  dist[K]=0
  que=[K]
  while que:
    label=que.pop(0)
    for i,c in path[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        que+=[i]
  return dist
 
N=int(input())
path=[ [] for i in range(N)]
for i in range(N-1):
  a,b,c=map(int,input().split())
  path[a-1]+=[[b-1,c]]
  path[b-1]+=[[a-1,c]]
Q,K=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(Q)]
distance=BFS(K-1,path,N)
for i in range(Q):
  print(distance[xy[i][0]-1]+distance[xy[i][1]-1])

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
input = stdin.readline
def BFS(K,path,N):
  """リストのリスト道順path,頂点の個数Nが与えられたとき, 頂点Kから各頂点までの距離をlistで返す"""
  dist=[-1]*N
  dist[K]=0
  que=[K]
  while que:
    label=que.pop(0)
    for i,c in path[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        que+=[i]
  return dist

N=int(input())
path=[ [] for i in range(N)]
for i in range(N-1):
  a,b,c=map(int,input().split())
  path[a-1]+=[[b-1,c]]
  path[b-1]+=[[a-1,c]]
Q,K=map(int,input().split())
distance=BFS(K-1,path,N)
for i in range(Q):
  x,y=map(int,input().split())
  print(distance[x-1]+distance[y-1])

Submission status: Time Limit Exceeded

Solution code:
def BFS(K,path,N):
  """リストのリスト道順path,頂点の個数Nが与えられたとき, 頂点Kから各頂点までの距離をlistで返す"""
  dist=[-1]*N
  dist[K]=0
  que=[K]
  while que:
    label=que.pop(0)
    for i,c in path[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        que+=[i]
  return dist

N=int(input())
path=[ [] for i in range(N)]
for i in range(N-1):
  a,b,c=map(int,input().split())
  path[a-1]+=[[b-1,c]]
  path[b-1]+=[[a-1,c]]
Q,K=map(int,input().split())
distance=BFS(K-1,path,N)
for i in range(Q):
  x,y=map(int,input().split())
  print(distance[x-1]+distance[y-1])

Submission status: Time Limit Exceeded

Solution code:
def BFS(K,path,N):
  """リストのリスト道順path,頂点の個数Nが与えられたとき, 頂点Kから各頂点までの距離をlistで返す"""
  dist=[-1]*N
  dist[K]=0
  que=[K]
  while que:
    label=que.pop(0)
    for i,c in path[label]:
      if dist[i]==-1:
        dist[i]=dist[label]+c
        que+=[i]
  return dist

N=int(input())
path=[ [] for i in range(N)]
for i in range(N-1):
  a,b,c=map(int,input().split())
  path[a-1]+=[[b-1,c]]
  path[b-1]+=[[a-1,c]]
Q,K=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(Q)]
distance=BFS(K-1,path,N)
for i in range(Q):
  print(distance[xy[i][0]-1]+distance[xy[i][1]-1])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
#幅優先探索
#TLE
import sys

N=input()

a=[[] for i in range(N+1)]
#隣接リスト
for i in range(N-1):
	x,y,z=list(map(int,raw_input().split()))
	a[x].append((y,z))
	a[y].append((x,z))

#print a

Q,K=list(map(int,raw_input().split()))


b=[]
for i in range(Q):
	b.append(map(int, raw_input().split()))
#print b



#訪問判別フラグ
F=(N+1)*[0]

#Queue
queue=[]

#距離
dist=[0 for i in range(N+1)]

p=-1
v=-1
length=0
#幅優先探索
queue.append(K)
while len(queue) != 0:
	v=queue.pop(0)
	F[v]=1
	for u,length in a[v]:
		if F[u]==0:
			queue.append(u)
			dist[u]=dist[v]+length


#print dist


for x in range(len(b)):
	print dist[ b[x][0] ]+ dist[ b[x][1] ]

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
#幅優先探索
import sys

N=input()

a=[[] for i in range(N+1)]
#隣接リスト
for i in range(N-1):
	x,y,z=list(map(int,raw_input().split()))
	a[x].append((y,z))
	a[y].append((x,z))

#print a

Q,K=list(map(int,raw_input().split()))


b=[]
for i in range(Q):
	b.append(map(int, raw_input().split()))
#print b



#訪問判別フラグ
F=(N+1)*[0]

#Queue
queue=[]

#距離
dist=[0 for i in range(N+1)]

#先頭から幅優先探索
queue.append(K)
while len(queue) != 0:
	#print queue
	v= queue.pop(0)
	#print "v::"+str(v)
	if F[v]==0:
		F[v]=1

		for u,length in a[v]:
			if F[u]==0:
				queue.append(u)
				dist[u]=dist[v]+length
				#print dist

#print dist


for x in range(len(b)):
	print dist[ b[x][0] ]+ dist[ b[x][1] ]

Submission status: Time Limit Exceeded

Solution code:
n = int(raw_input())
r = range(n)
t = [[10**15 for _ in r] for _ in r]
for i in r:
    t[i][i] = 0
for _ in range(n-1):
    a,b,c = map(int, raw_input().split())
    t[a-1][b-1] = c
    t[b-1][a-1] = c
for p in r:
    for s in r:
        for e in r:
            if t[s][e] > t[s][p] + t[p][e]:
                t[s][e] = t[s][p] + t[p][e]
q,k = map(int, raw_input().split())
for _ in range(q):
    x,y = map(int, raw_input().split())
    print t[x-1][k-1] + t[k-1][y-1]

Submission status: Time Limit Exceeded

Solution code:
n = int(raw_input())
t = [[10**15 for _ in range(n)] for _ in range(n)]
for i in range(n):
    t[i][i] = 0
for _ in range(n-1):
    a,b,c = map(int, raw_input().split())
    t[a-1][b-1] = c
    t[b-1][a-1] = c
for p in range(n):
    for s in range(n):
        for e in range(n):
            if t[s][e] > t[s][p] + t[p][e]:
                t[s][e] = t[s][p] + t[p][e]
q,k = map(int, raw_input().split())
for _ in range(q):
    x,y = map(int, raw_input().split())
    print t[x-1][k-1] + t[k-1][y-1]

Submission status: Time Limit Exceeded

Solution code:
import sys
from scipy.sparse import*
f=lambda*z:map(int,sys.stdin.readline().split())
n,=f();a,b,c=zip(*map(f,[0]*~-n));q,k=f()
z=csgraph.dijkstra(coo_matrix((c,(a,b)),[n+1]*2),0,k)
for _ in range(q):x,y=f();print int(z[x]+z[y])

Submission status: Time Limit Exceeded

Solution code:
import sys
from scipy.sparse import*
f=lambda*z:map(int,sys.stdin.readline().split())
n,=f();a,b,c=zip(*map(f,[0]*~-n));q,k=f()
z=csgraph.dijkstra(csc_matrix((c,(a,b)),[n+1]*2),0,k)
for _ in range(q):x,y=f();print int(z[x]+z[y])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(int(1e5+10))

def search_dist(g, dist, e):
    for b, c in g.get(e):
        if dist[b] is not None:
            continue
        dist[b] = dist[e] + c
        search_dist(g, dist, b)

def main():
    g = {}
    N = int(input())
    for _ in range(N-1):
        a, b, c = list(map(int, input().split(' ')))
        g[a] = g.get(a, []) + [(b, c)]
        g[b] = g.get(b, []) + [(a, c)]
    Q, K = list(map(int, input().split(' ')))
    dist = [None]*(N+1)
    dist[K] = 0
    search_dist(g, dist, K)
    cood = []
    for _ in range(Q):
        cood.append(list(map(int, input().split(' '))))

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from scipy.sparse import*
f=lambda*z:map(int,sys.stdin.readline().split())
n,=f();a,b,c=zip(*map(f,[0]*~-n));q,k=f()
z=csgraph.dijkstra(csr_matrix((c,(a,b)),[n+1]*2),0,k)
for _ in range(q):x,y=f();print int(z[x]+z[y])

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse import*
f=lambda*z:map(int,input().split())
n,=f();a,b,c=zip(*map(f,[0]*~-n));q,k=f()
z=csgraph.dijkstra(csr_matrix((c,(a,b)),[n+1]*2),0,k)
for _ in range(q):x,y=f();print(int(z[x]+z[y]))

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse import*
f=lambda*z:map(int,raw_input().split())
n,=f();a,b,c=zip(*map(f,[0]*~-n));q,k=f()
z=csgraph.dijkstra(csr_matrix((c,(a,b)),[n+1]*2),0,k)
for _ in range(q):x,y=f();print int(z[x]+z[y])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
path = [[0 for i in range(n)] for j in range(n)]

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


q, k = map(int, input().split())
distance = [None] * n
distance[k-1] = 0
queue = [k-1]
while(len(queue)):
    p = queue.pop()
    for i in range(n):
        if(path[min(i,p)][max(i,p)]!=0 and distance[i] == None):
            distance[i] = distance[p] + path[min(i,p)][max(i,p)]
            queue.append(i)

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

Submission status: Time Limit Exceeded

Solution code:
#! /usr/bin/env python3
import sys

def main():
    D = []
    S = [x for x in sys.stdin]
    N = int(S.pop(0))
    M = [0] * (N+1)
    ksigh = [1] * (N+1)
    sumk = 0
    for i in range(N-1):
        a, b, c = map(int, S[i].split())
        M[b] = (i, a)
        D.append(c)
    Q, K = map(int, S[N-1].split())
    tk = K
    kmemo = {}
    while M[tk]:
        a, tk = M[tk]
        ksigh[a] = -1
        kmemo[a] = sumk
        sumk += D[a]
    memo = {}
    for i in range(N, N+Q):
        x, y = map(int, S[i].split())
        tx, ty = x, y
        if x not in memo:
            xsum = 0
            p = -1
            t = M[tx]
            while t:
                a, tx = t
                if ksigh[a] < 0:
                    p = a
                    break
                xsum += D[a]
                t = M[tx]
            t = M[K]
            if p in kmemo:
                xsum += kmemo[p]
            else:
                xsum += sumk
            memo[x] = xsum
        if y not in memo:
            ysum = 0
            p = -1
            t = M[ty]
            while t:
                a, ty = t
                if ksigh[a] < 0:
                    p = a
                    break
                ysum += D[a]
                t = M[ty]
            t = M[K]
            if p in kmemo:
                ysum += kmemo[p]
            else:
                ysum += sumk
            memo[y] = ysum
        sys.stdout.write(str(memo[x] + memo[y]) + '\n')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq
import copy
inf =10**15+7
N = int(input())
A = [ [inf for i in range(N)] for j in range(N)]
for n in range(N-1):
  a,b,c=map(int,input().split())
  A[a-1][b-1] = c
  A[b-1][a-1] = c
 
Q,K = map(int,input().split())


def dijkstra(start):
    INF=1e+09
    SUM=[0 for _ in range(n)]
        
    # グラフのノード数
    num = len(A)
    # 始点から各頂点までの最短距離を格納する
    dist = [float('inf') for i in range(num)]
    #最短経路における，その頂点の前の頂点のIDを格納する
    prev = ["null" for i in range(num)] 

    #始点
    dist[start] = 0
    #qの初期化
    q = list(range(num))
    
    while len(q) != 0:
      tmp=[dist[qq] for qq in q]
      src = q.pop(tmp.index(min(tmp)))
      # 他の頂点の探索
      for dest in range(num):
        cost = A[src][dest]
        # 道が繋がっているかつ、今までより小さいコストでいけるとき
        if cost != float('inf') and dist[dest] > dist[src] + cost:
          dist[dest] = dist[src] + cost 
          prev[dest] = src
    
    return dist
    
dist = dijkstra(K-1)

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

Submission status: Time Limit Exceeded

Solution code:
import collections

def bfs(tree, s, distance):
    queue = [s]
    distance[s] = 0

    while queue:
        v = queue.pop(0)
        v_c = distance[v]
        for node, cost in tree[v]:
            if distance[node] == -1:
                distance[node] = v_c + cost
                queue.append(node)

N = int(input())

Tree = collections.defaultdict(list)

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

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

distance = collections.defaultdict(lambda : -1)
bfs(Tree, k, distance)

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

Submission status: Time Limit Exceeded

Solution code:
import collections

#def bfs(tree, s, distance):
#    queue = [s]
#    distance[s] = 0
#
#    while queue:
#        v = queue.pop(0)
#        for node, cost in tree[v]:
#            if distance[node] == -1:
#                distance[node] = distance[v] + cost
#                queue.append(node)

N = int(input())

Tree = collections.defaultdict(list)

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

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

distance = collections.defaultdict(lambda : -1)
#bfs(Tree, k, distance)
queue = [k]
distance[k] = 0
while queue:
    v = queue.pop(0)
    for node, cost in Tree[v]:
        if distance[node] == -1:
            distance[node] = distance[v] + cost
            queue.append(node)

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

Submission status: Time Limit Exceeded

Solution code:
import collections

N = int(input())

Tree = collections.defaultdict(list)

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

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

def bfs(tree, s, distance):
    queue = [s]
    distance[s] = 0

    while queue:
        v = queue.pop(0)
        for node, cost in tree[v]:
            if distance[node] == -1:
                distance[node] = distance[v] + cost
                queue.append(node)

distance = collections.defaultdict(lambda : -1)
bfs(Tree, k, distance)

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

Submission status: Time Limit Exceeded

Solution code:
import collections

N = int(input())

Tree = collections.defaultdict(list)

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

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

def bfs(tree, s, distance):
    queue = [s]
    distance[s] = 0

    while queue:
        v = queue.pop(0)
        for child in tree[v]:
            if distance[child[0]] == -1:
                distance[child[0]] = distance[v] + child[1]
                queue.append(child[0])

distance = collections.defaultdict(lambda : -1)
bfs(Tree, k, distance)

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

Submission status: Time Limit Exceeded

Solution code:
#! /usr/bin/env python3
import sys

def main():
    L = []
    S = list(sys.stdin)
    N = int(S.pop(0))
    D = [0] * (N+1)
    k = [1] * (N+1)
    sumk = 0
    for i in range(N-1):
        a, b, c = map(int, S[i].split())
        D[b] = (i, a)
        L.append(c)
    Q, K = map(int, S[N-1].split())
    while D[K]:
        a, K = D[K]
        k[a] = -1
        sumk += L[a]
    memo = {}
    for i in range(N, N+Q):
        x, y = map(int, S[i].split())
        tx, ty = x, y
        if x not in memo:
            xsum = sumk
            t = D[tx]
            while t:
                a, tx = t
                xsum += L[a] * k[a]
                t = D[tx]
            memo[x] = xsum
        if y not in memo:
            ysum = sumk
            t = D[ty]
            while t:
                a, ty = t
                ysum += L[a] * k[a]
                t = D[ty]
            memo[y] = ysum
        sys.stdout.write(str(memo[x] + memo[y]) + '\n')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [0]*n
b = [0]*n
c = [0]*n

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

def askdis(st,cur,en,d=0):
    if cur == en:
        dp[st-1][en-1]=dp[en-1][st-1]=min(dp[st-1][en-1],d)
        return

    for i in range(n-1):
        if flag[i]:
            flag[i]=False
            if a[i]==cur :
                askdis(st,b[i],en,d+c[i])
            if b[i]==cur :
                askdis(st,a[i],en,d+c[i])
            flag[i]=True


dp = [ [10**10]*(n) for _ in range(n)]

for i in range(1,n+1):
    for j in range(i+1,n+1):
        askdis(i,i,j)

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

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

Submission status: Time Limit Exceeded

Solution code:
#! /usr/bin/env python3
import sys

def main():
    L = []
    S = [x for x in sys.stdin]
    N = int(S.pop(0))
    D = [0] * (N+1)
    k = [1] * (N+1)
    sumk = 0
    for i in range(N-1):
        a, b, c = map(int, S[i].split())
        D[b] = (i, a)
        L.append(c)
    Q, K = map(int, S[N-1].split())
    while D[K]:
        a, K = D[K]
        k[a] = -1
        sumk += L[a]
    memo = {}
    for i in range(N, N+Q):
        x, y = map(int, S[i].split())
        tx, ty = x, y
        if x not in memo:
            xsum = sumk
            t = D[tx]
            while t:
                a, tx = t
                xsum += L[a] * k[a]
                t = D[tx]
            memo[x] = xsum
        if y not in memo:
            ysum = sumk
            t = D[ty]
            while t:
                a, ty = t
                ysum += L[a] * k[a]
                t = D[ty]
            memo[y] = ysum
        sys.stdout.write(str(memo[x] + memo[y]) + '\n')

if __name__ == '__main__':
    main()