Problem:


Score : 400 points

Problem Statement

You are given a tree with N vertices.

Here, a tree is a kind of graph, and more specifically, a connected undirected graph with N-1 edges, where N is the number of its vertices.

The i-th edge (1≤i≤N-1) connects Vertices a_i and b_i, and has a length of c_i.

You are also given Q queries and an integer K. In the j-th query (1≤j≤Q):

find the length of the shortest path from Vertex x_j and Vertex y_j via Vertex K.

Constraints

3≤N≤10^5 

1≤a_i,b_i≤N (1≤i≤N-1) 

1≤c_i≤10^9 (1≤i≤N-1) 

The given graph is a tree.

1≤Q≤10^5 

1≤K≤N 

1≤x_j,y_j≤N (1≤j≤Q) 

x_j≠y_j (1≤j≤Q) 

x_j≠K,y_j≠K (1≤j≤Q) 

Input

Input is given from Standard Input in the following format:  

N  
a_1 b_1 c_1  
:  
a_{N-1} b_{N-1} c_{N-1}
Q K
x_1 y_1
:  
x_{Q} y_{Q}

Output

Print the responses to the queries in Q lines.

In the j-th line j(1≤j≤Q), print the response to the j-th query.

Sample Input 1

5
1 2 1
1 3 1
2 4 1
3 5 1
3 1
2 4
2 3
4 5

Sample Output 1

3
2
4

The shortest paths for the three queries are as follows:

Query 1: Vertex 2 → Vertex 1 → Vertex 2 → Vertex 4 : Length 1+1+1=3 

Query 2: Vertex 2 → Vertex 1 → Vertex 3 : Length 1+1=2 

Query 3: Vertex 4 → Vertex 2 → Vertex 1 → Vertex 3 → Vertex 5 : Length 1+1+1+1=4 

Sample Input 2

7
1 2 1
1 3 3
1 4 5
1 5 7
1 6 9
1 7 11
3 2
1 3
4 5
6 7

Sample Output 2

5
14
22

The path for each query must pass Vertex K=2.

Sample Input 3

10
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000
6 7 1000000000
7 8 1000000000
8 9 1000000000
9 10 1000000000
1 1
9 10

Sample Output 3

17000000000



Sample input:
5
1 2 1
1 3 1
2 4 1
3 5 1
3 1
2 4
2 3
4 5


Sample output:
3
2
4

Submission status: Wrong Answer

Solution code:
#070-D
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return input()

#ベルマンフォード法
#E,vはedge、vertexの数
v=I()
E=v-1
e=[]
for i in range(E): #eの各要素は[始点,終点,コスト]
    f,t,c=map(int,input().split())
    e.append([f-1,t-1,c])
d=[None for i in range(v)]
def sp(s): #sは始点、dに各頂点への最短距離が格納される
    for i in range(v):
        d[i]=float('INF')
    d[s]=0
    while True:
        update=False
        for i in range(E):
            if d[e[i][0]]!=float('INF') and d[e[i][1]]>d[e[i][0]]+e[i][2]:
                d[e[i][1]]=d[e[i][0]]+e[i][2]
                update=True
        if update==False:
            break
q,k=IL()
sp(k-1)
for i in range(q):
    x,y=IL()
    print(d[x-1]+d[y-1])

Submission status: Wrong Answer

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
    dd = [float("inf")] * N
    Q.append(start)
    dd[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
                dd[b] = dd[a] + c
    return dd

def DFS(N, graph, a, p, d):
    dd[a] = d
    for b, c in graph[a]:
        if b == p or dd[b] != 0:
            continue
        else:
            DFS(N, graph, b, a, d + c)

N = int(input())

sys.setrecursionlimit(100)

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())
dd = [0] * N

try:
    DFS(N, graph, K-1, -1, 0)
except:
    BFS(N, graph, K-1)

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

Submission status: Wrong Answer

Solution code:
class WeightsUnionfind:
  def __init__(self,n):
    self.Tree=[i for i in range(n)]
    self.dWeights=[0]*n
    
  def weigh(self,x):
    if x==self.Tree[x]:
      return 0
    else:
      w=self.weigh(self.Tree[x])+self.dWeights[x]
      return w

  def unite(self,x,y,w):
    if x==K-1:
        self.Tree[y]=x
        self.dWeights[y]=w
    elif y==K-1:
        self.Tree[x]=y
        self.dWeights[x]=w
    else:
        self.Tree[y]=x
        self.dWeights[y]=w
          
N=int(input())
List=[[int(i) for i in input().split()] for i in range(N-1)]
Q,K=map(int,input().split())
wuf=WeightsUnionfind(N)
for i in range(N-1):
  a,b,c=List[i][0],List[i][1],List[i][2]
  wuf.unite(a-1,b-1,c)
path=[0]*N
for i in range(N):
  path[i]=abs(wuf.weigh(i))
for q in range(Q):
  x,y=map(int,input().split())
  print(path[x-1]+path[y-1])

Submission status: Wrong Answer

Solution code:
class WeightsUnionfind:
  def __init__(self,n):
    self.Tree=[i for i in range(n)]
    self.dWeights=[0]*n
    self.rank=[0]*n
    self.wrong=0

  def find(self,x):
    if x==self.Tree[x]:
      return x
    else:
      root=self.find(self.Tree[x])
      self.dWeights[x]=self.weigh(x)
      self.Tree[x]=root
      return root
  
  def weigh(self,x):
    if x==self.Tree[x]:
      return 0
    else:
      w=self.weigh(self.Tree[x])+self.dWeights[x]
      return w

  def unite(self,x,y,w):
    s1=self.find(x)
    s2=self.find(y)
    if s1==s2:
      if self.weigh(y)-self.weigh(x)!=w:
        self.wrong=1
    else:
      if self.rank[s1]>self.rank[s2]:
        self.Tree[s2]=s1
        self.dWeights[s2]=self.weigh(x)-self.weigh(y)+w
      elif self.rank[s1]<self.rank[s2]:
        self.Tree[s1]=s2
        self.dWeights[s1]=self.weigh(y)-self.weigh(x)-w
      else:
        self.Tree[s2]=s1
        self.rank[s1]+=1
        self.dWeights[s2]=self.weigh(x)-self.weigh(y)+w
          
N=int(input())
wuf=WeightsUnionfind(N)
for i in range(N-1):
  a,b,c=map(int,input().split())
  wuf.unite(a-1,b-1,c)
Q,K=map(int,input().split())
path=[0]*N
for i in range(N):
  path[i]=abs(wuf.weigh(K-1)+wuf.weigh(i))
for q in range(Q):
  x,y=map(int,input().split())
  print(path[x-1]+path[y-1])

Submission status: Wrong Answer

Solution code:
class WeightsUnionfind:
  def __init__(self,n):
    self.Tree=[i for i in range(n)]
    self.dWeights=[0]*n
    self.rank=[0]*n
    self.wrong=0

  def find(self,x):
    if x==self.Tree[x]:
      return x
    else:
      root=self.find(self.Tree[x])
      self.dWeights[x]=self.weigh(x)
      self.Tree[x]=root
      return root
  
  def weigh(self,x):
    if x==self.Tree[x]:
      return 0
    else:
      w=self.weigh(self.Tree[x])+self.dWeights[x]
      return w

  def unite(self,x,y,w):
    s1=self.find(x)
    s2=self.find(y)
    if s1==s2:
      if self.weigh(y)-self.weigh(x)!=w:
        self.wrong=1
    else:
      if self.rank[s1]>self.rank[s2]:
        self.Tree[s2]=s1
        self.dWeights[s2]=self.weigh(x)-self.weigh(y)+w
      elif self.rank[s1]<self.rank[s2]:
        self.Tree[s1]=s2
        self.dWeights[s1]=self.weigh(y)-self.weigh(x)-w
      else:
        self.Tree[s2]=s1
        self.rank[s1]+=1
        self.dWeights[s2]=self.weigh(x)-self.weigh(y)+w
          
N=int(input())
wuf=WeightsUnionfind(N)
for i in range(N-1):
  a,b,c=map(int,input().split())
  wuf.unite(a-1,b-1,c)
Q,K=map(int,input().split())
path=[0]*N
for i in range(N):
  path[i]=abs(wuf.weigh(K-1)-wuf.weigh(i))
for q in range(Q):
  x,y=map(int,input().split())
  print(path[x-1]+path[y-1])

Submission status: Wrong Answer

Solution code:
#dojkstra (prioroty queue ver.)
import queue
G=[]
#infの値に注意
inf=10**9
#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に直して入れる
    print(d[xt-1]+d[yt-1])

Submission status: Wrong Answer

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

klist = [-1]
for v in node:
    if K != v:
        klist.append(dfs(L,K,v))
    else:
        klist.append(-1)

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)

N = int(input())
X, Y = [], []

tree = {key+1: [] for key in range(N)}  # 木構造はノードをキーにする辞書にしておく
# 必要なのは、あるノードを指定したときに、隣り合うノードと、コスト
#[(隣のノード, コスト)]の順で格納する

for n in range(N - 1):
    a, b, c = list(map(int, input().split()))
    tree[a].append((b, c))
    tree[b].append((a, c))  # 方向に依存しない格納

# for n in tree.keys():
#     tree[n] = list(set(tree[n]))  # 重複を削除
# こいつが原因ではない

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

cost = {}  # Kがkeyに行くまでにかかるコストの辞書


def dfs(v, p, d):
    """
    深さ優先探索
    再帰的に処理する
    args:
        v: 現在の頂点
        p: vの親(訪問元)
        d: 現在の距離
    """
    cost[v] = d
    for i, co in tree[v]:
        if i == p:
            continue
        dfs(i, v, d + co)


dfs(K, -1, 0)

print(cost)
ans = []
for q in range(Q):
    x, y = list(map(int, input().split()))
    ans.append(cost[x] + cost[y])

for a in ans:
    print(a)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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))
    
print (G)
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: Wrong Answer

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

check(s,0)

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

Submission status: Wrong Answer

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


def find(x):	#xの根を返す
	global table
	global diff_weight

	if table[x] == x:
		return x
	else:
		root = find(table[x])
		diff_weight[x] += diff_weight[table[x]] #親の更新に伴う 重みの更新
		table[x] = root	#親の更新(根を直接親にして参照距離を短く)
		return table[x]

def union(x,y,w):	#xとyを diff(x,y)=w で繋げる
	w = w - weight(y) + weight(x)
	x = find(x)
	y = find(y)

	if x == y:
		return

	if rank[x] < rank[y]:
		x,y = y,x
		w = -w

	table[y] = x
	diff_weight[y] = w

	if rank[x] == rank[y]:
			rank[y] += 1

def check(x,y): #xとyか繋がっているか -> return bool
	if find(x) == find(y):
		return True
	else:
		return False

def weight(x):
	find(x)	#経路圧縮
	return diff_weight[x]

def diff(x,y): # weight(y)-weight(x)  (繋がってる前提)
	return abs(weight(y) - weight(x))


N = int(input())

table = [i for i in range(N)]	#木の親 table[x] == x なら根
rank  = [1 for i in range(N)]	#木の長さ
diff_weight = [0 for i in range(N)]


for i in range(N-1):
	a,b,c = inpl()
	a -= 1
	b -= 1
	union(a,b,c)

Q,s = inpl()
s -= 1
ss = []
root = find(0)

for i in range(N):
	ss.append(diff(s,root) + diff(i,root))

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)

N = int(input())
X = [[] for _ in range(N)]

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

cost = [-1]*N
def calc(i,c):
    # 指定の頂点までのコストを代入
    cost[i] = c
    # 頂点から移動できる頂点があれば
    for ni,nc in X[i]:
        # 初期状態のままなら計算
        if cost[ni] == -1:
            calc(ni,c+nc)

Q,K = map(int,input().split())
# 事前計算
calc(K-1,0)

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

Submission status: Wrong Answer

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

Q, K = map(int, input().split())
checked = set([K])
length = [0]*(N+1)
check = set([K])

while len(checked) < N:
    nextcheck = set()
    for i in check:
        for j in treedic[i].keys():
            length[j] = length[i] + treedic[i][j]
            checked.add(j)
            nextcheck.add(j)
    check = nextcheck

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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from collections import deque
def inpl(): return map(int, input().split())
N = int(input())

G = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b, c = inpl()
    G[a].append((b, c))
    G[b].append((a, c))

D = [0] * (N+1)
Q, K = inpl()
DQ = deque([K])
visited = [False]*(N+1)

while DQ:
    p = DQ.popleft()
    visited[p] = True
    for q, d in G[p]:
        if not visited[q]:
            D[q] = D[p] + c
            DQ.append(q)

for _ in range(Q):
    x, y = inpl()
    print(D[x] + D[y])

Submission status: Wrong Answer

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

from enum import Enum
from heapq import heappush, heappop


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.d = [Sssp.INFINITY] * num_of_nodes  # 始点からの重み
        self.adj = [[] for _ in range(num_of_nodes)]
        self.make_adj(data)

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


    def dijkstra(self, start):
        self.d[start] = 0
        pq = []
        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, (c, 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: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
http://abc070.contest.atcoder.jp/tasks/abc070_d
"""
# TLEするので、ダイクストラのアルゴリズムからの高速化が必要

from enum import Enum
from heapq import heappush, heappop


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.d = [Sssp.INFINITY] * num_of_nodes  # 始点からの重み
        # self.p = [-1] * num_of_nodes  # 各頂点の親の番号を記録するための配列
        self.adj = [[] for _ in range(num_of_nodes)]
        self.make_adj(data)

    def make_adj(self, data):
        # 隣接リストの作成
        for d in data:
            f, t, c = d
            self.adj[f].insert(0, (t, c))
            self.adj[t].insert(0, (f, c))


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

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

            for v, cost in self.adj[u]:
                if self.color[v] == Sssp.Status.black:
                    continue
                if self.d[v] > self.d[u] + cost:
                    self.d[v] = self.d[u] + cost
                    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: Wrong Answer

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


test =False
if test:
    N = 7
    graph[1] = [(2, 1), (5, 1)]
    graph[2] = [(1, 1), (3, 1), (4, 1)]
    graph[3] = [(2, 1)]
    graph[4] = [(2, 1)]
    graph[5] = [(1, 1), (6,1), (7,1)]
    graph[6] = [(5, 1)]
    graph[7] = [(5, 1)]
    print solve(2, 3)
    print solve(2, 4)
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)
    for _ in range(Q):
        x, y = raw_input().split()
        x = int(x)
        y = int(y)
        print solve(x, K) + solve(K, y)

Submission status: Wrong Answer

Solution code:
import sys

import Queue

q = Queue.Queue()

cache = {}
graph = {}

def solve(x, y):
    distance = cache.get((x,y))
    if distance is not None:
        return distance
    q.put((x, 0, []))
    while not q.empty():
        start, dist, path = q.get()
        for neighbor, next_dist in graph[start]:
            cache[(x, neighbor)] = dist + next_dist
            cache[(neighbor, x)] = dist + next_dist
            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]))


test =False
if test:
    N = 5
    graph[1] = [(2, 1), (3, 1)]
    graph[2] = [(1, 1), (4, 1)]
    graph[3] = [(1, 1), (5, 1)]
    graph[4] = [(2, 1)]
    Q = 3
    K = 1
    print solve(4, 1)
    print solve(1, 5)
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))
        cache[(a, b)] = c
        cache[(b, a)] = c

    Q, K = raw_input().split()
    Q = int(Q)
    K = int(K)
    for _ in range(Q):
        x, y = raw_input().split()
        x = int(x)
        y = int(y)
        print solve(x, K) + solve(K, y)

Submission status: Wrong Answer

Solution code:
import sys

import Queue

q = Queue.Queue()

cache = {}
graph = {}

def solve(x, y):
    distance = cache.get((x,y))
    if distance is not None:
        return distance
    q.put((x, 0, []))
    while not q.empty():
        items = q.get()
        start, dist, path = items
        #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]))


test = False
if test:
    N = 5
    graph[1] = [(2, 1), (3, 1)]
    graph[2] = [(1, 1), (4, 1)]
    graph[3] = [(1, 1), (5, 1)]
    graph[4] = [(2, 1)]
    Q = 3
    K = 1
    print solve(4, 1)
    print solve(1, 5)
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))
        cache[(a, b)] = c
        cache[(b, a)] = c

    Q, K = raw_input().split()
    Q = int(Q)
    K = int(K)
    for _ in range(Q):
        x, y = raw_input().split()
        x = int(x)
        y = int(y)
        print solve(x, K) + solve(K, y)

Submission status: Wrong Answer

Solution code:
from collections import deque 

n = int(input())

preroots = []
preroots_appd = preroots.append

for i in range(n-1):
    preroots_appd(list(map(int,input().split())))
    
roots = [[] for x in range(n+1)]

for i in preroots:
    roots[i[0]].append((i[1],i[2]))         
    roots[i[1]].append((i[0],i[2]))     
         
QK = list(map(int,input().split()))         
query = []

query_appd = query.append
for i in range(QK[0]):
    query_appd(list(map(int,input().split())))
        
    
distfrom_K = [-1 for x in range(n+1)]
distfrom_K[QK[1]] = 0          

q = deque()
q.append(QK[1])

while(len(q)):
    currentNode = q.popleft()
    for i in roots[currentNode]:
        if distfrom_K[i[0]] != -1:continue
        q.append(i[0])
        distfrom_K[i[0]] = distfrom_K[currentNode] + i[0]

for i in query:
    print(distfrom_K[i[0]]+distfrom_K[i[1]])

Submission status: Wrong Answer

Solution code:
from collections import deque 

n = int(input())

preroots = []
preroots_appd = preroots.append

for i in range(n-1):
    preroots_appd(list(map(int,input().split())))
    
roots = [[] for x in range(n+1)]

for i in preroots:
    roots[i[0]].append((i[1],i[2]))         
    roots[i[1]].append((i[0],i[2]))     
         
QK = list(map(int,input().split()))         
query = []

query_appd = query.append
for i in range(QK[0]):
    query_appd(list(map(int,input().split())))
        
    
distfrom_K = [-1 for x in range(n+1)]
distfrom_K[QK[1]] = 0          

q = deque()
q.append(QK[1])

while(len(q)):
    currentNode = q.popleft()
    for i in roots[currentNode]:
        if distfrom_K[i[0]] != -1:continue
        q.append(i[0])
        distfrom_K[i[0]] = distfrom_K[currentNode] + roots[i[0]][0][1]

for i in query:
    print(distfrom_K[i[0]]+distfrom_K[i[1]])

Submission status: Wrong Answer

Solution code:
import heapq
from collections import defaultdict

INF = 1e11

N = int(input())
Adj_list = defaultdict(set)

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

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

def dijkstra(x, vertex):
    d = [INF] * x
    d[vertex] = 0
    hq = [(0, vertex)] # (distance, v)の順。一般的にヒープは(key, 要素)のタプルをpush, popする。
    
    while hq:
        u = heapq.heappop(hq)[1]
        for (v, c) in Adj_list[u]:
            if d[v] > d[u] + c:
                d[v] = d[u] + c
                heapq.heappush(hq, (d[u] + c, v))
                
    return d

distance = dijkstra(N, K-1)

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

Submission status: Wrong Answer

Solution code:
import heapq
from collections import defaultdict

INF = 1e9

N = int(input())
Adj_list = defaultdict(set) # 隣接リスト

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

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

def dijkstra(x, vertex):
    d = [INF] * x
    d[vertex] = 0
    hq = [(0, vertex)] # (distance, v)の順。一般的にヒープは(key, 要素)のタプルをpush, popする。
    
    while hq:
        u = heapq.heappop(hq)[1]
        for (v, c) in Adj_list[u]:
            if d[v] > d[u] + c:
                d[v] = d[u] + c
                heapq.heappush(hq, (d[u] + c, v))
                
    return d

distance = dijkstra(N, K-1)

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

Submission status: Wrong Answer

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]

#Stack
S=[]

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

#先頭から深さ優先探索
S.append(1)
former_v=0
v=0
while len(S) != 0:
	v=S.pop()
	
	if F[v]==0:
		F[v]=1

		for u,length in a[v]:
			if F[u]==0:
				S.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: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
#Python
import sys


N=input()
#print N


M= 9999999999
a=[[M for i3 in range(N+1)] for i in range(N+1)]

#隣接リスト
for i in range(N-1):
	x,y,z=list(map(int,raw_input().split()))
	a[x][y]=z
	a[y][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()))




#確定フラグ
v=(N+1)*[0]

#距離
leng=(N+1)*[M]
Start=K
leng[Start]=0


Min= M
p=Start

#Start地点には事前に確定フラグをONにしておく
v[Start]=1

for j in range(N-1):
	#pを経由してkに至る経路が最短経路となれば、更新
	for k in range(1,N+1):
		#print "k::"+str(k)
		#print "a[p][k] ::"+str(a[p][k] )
		if leng[p]+a[p][k] < leng[k]:
			leng[k]=leng[p]+a[p][k]


	#print "#leng"
	#print leng



	#最小距離となる接点を、確定フラグが立っていない点（v[k]=0)から探す
	Min=M
	for k in range(1,N+1):
		if v[k]==0 and leng[k]< Min:
			p=k
			Min=leng[k]

	#print "#p"
	#print p
	#print "#Min"
	#print Min

	#最小の接点を確定する
	v[p]=1
	#print "#v"
	#print v


#print "#b"
#print b

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

Submission status: Wrong Answer

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 z[x]+z[y]

Submission status: Wrong Answer

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 for _ in range(N+1)]
    k = [1 for _ in range(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())
    tk = K
    kmemo = {}
    while D[tk]:
        a, tk = D[tk]
        k[a] = -1
        kmemo[a] = sumk
        sumk += L[a]
    kmemo[0] = sumk
    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 = p = 0
            t = D[tx]
            while t:
                a, tx = t
                if k[a] < 0:
                    p = a
                    break
                xsum += L[a]
                t = D[tx]
            memo[x] = xsum + kmemo[p]
        if y not in memo:
            ysum = p = 0
            t = D[ty]
            while t:
                a, ty = t
                if k[a] < 0:
                    p = a
                    break
                ysum += L[a]
                t = D[ty]
            memo[y] = ysum + kmemo[p]
        sys.stdout.write(str(memo[x] + memo[y]) + '\n')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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())
    tk = K
    kmemo = {}
    while D[tk]:
        a, tk = D[tk]
        k[a] = -1
        kmemo[a] = sumk
        sumk += L[a]
    kmemo[0] = sumk
    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 = p = 0
            t = D[tx]
            while t:
                a, tx = t
                if k[a] < 0:
                    p = a
                    break
                xsum += L[a]
                t = D[tx]
            memo[x] = xsum + kmemo[p]
        if y not in memo:
            ysum = p = 0
            t = D[ty]
            while t:
                a, ty = t
                if k[a] < 0:
                    p = a
                    break
                ysum += L[a]
                t = D[ty]
            memo[y] = ysum + kmemo[p]
        sys.stdout.write(str(memo[x] + memo[y]) + '\n')

if __name__ == '__main__':
    main()