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:
from collections import deque

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

    while queue:
        label = queue.pop()

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

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

    return

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

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

bfs(k - 1)

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

Submission status: Time Limit Exceeded

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

# Set max recursion limit
sys.setrecursionlimit(1000000)


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


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


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


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

dp = None
D = None
D_dfs_d = None


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

    D_dfs_d[v] = dist

    for i, d in enumerate(D[v]):
        if d != -1 and i != pre:
            dfs_d(i, v, dist + d)

    return


def main():
    global D
    global D_dfs_d

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

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

    Q, K = li_input()

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

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


main()

Submission status: Time Limit Exceeded

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

# Set max recursion limit
sys.setrecursionlimit(10000)


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


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


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


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

dp = None


def count_from_K(D, N, K):
    d_from_k = [-1] * (N + 1)
    d_from_k[K] = 0

    current_positions = [(K, 0)]
    reached = [False] * (N + 1)
    reached[K] = True
    while len(current_positions) != 0:
        new_current_positions = []
        for current_position, current_distance in current_positions:
            for node_num, distance_from_current_position in enumerate(
                    D[current_position]):
                if distance_from_current_position != -1 and not reached[node_num]:
                    d_from_k[
                        node_num] = current_distance + distance_from_current_position
                    new_current_positions.append(
                        (node_num,
                         current_distance + distance_from_current_position))
                    reached[node_num] = True

        current_positions = new_current_positions[:]

    return d_from_k


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

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

    Q, K = li_input()

    # Kから各頂点までの長さをWFSで求める
    d_from_k = count_from_K(D, N, K)

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


main()

Submission status: Time Limit Exceeded

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 -> b コスト:c の経路
	lines[a].add((b,c))
	lines[b].add((a,c))

Q,s = inpl()

weight = [-1]*(N+1)
weight[s] = 0

q = [[0,s]]
heapq.heapify(q)

while q:
	w0,s = heapq.heappop(q)
	for line in list(lines[s]):
		t = line[0]
		w = w0 + line[1]
		if weight[t] == -1 or weight[t] > w: #未探索orより小さい
			heapq.heappush(q, [w,t])
			weight[t] = w

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

Submission status: Time Limit Exceeded

Solution code:
class DFS:
    def __init__(self, N):
        self.N = N
        self.visited = []
        self.depth = [0 for i in range(N)]
        self.edge = [[] for i in range(N)]
        self.graph = [[False for i in range(N)] for j in range(N)]

    def dfs2(self, v, p, d):
        self.depth[v] = d
        for e in self.edge[v]:
            if (e[0] == p):
                continue
            self.dfs2(e[0], v, d+e[1])

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

Q,K = map(int,input().split())
dfs.dfs2(K-1,-1,0)
for _ in range(Q):
    x,y = map(int, input().split())
    print(dfs.depth[x-1]+dfs.depth[y-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import heapq

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

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


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

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

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

    return dist[y]


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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

    while queue:
        label = queue.pop()

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

            for v in d[label]:
                if v[0] not in visited:
                    dist[v[0]] = dist[label] + v[1]
                    queue.appendleft(v[0])

    return

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

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

bfs(k - 1)

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
g = [[] for _ in range(0,N+1)]
for i in range(0,N-1):
    a,b,c = map(int,input().split())
    g[a].append((b,c))
    g[b].append((a,c))
Q,K = map(int,input().split())
xy = []
for i in range(0,Q):
    x,y = map(int,input().split())
    xy.append((x,y))

d = [-1 for _ in range(0,N+1)]
d[K] = 0
queue = []
queue.append((K,g[K]))
while queue:
    start,edge = queue.pop(0)
    for to,cost in edge:
        if d[to] != -1:
            continue
        d[to] = d[start] + cost
        queue.append((to,g[to]))

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
g = [[] for _ in range(0,N+1)]
for i in range(0,N-1):
    a,b,c = map(int,input().split())
    g[a].append((b,c))
    g[b].append((a,c))
Q,K = map(int,input().split())
xy = []
for i in range(0,Q):
    x,y = map(int,input().split())
    xy.append((x,y))

#dijkstra
d = [float("inf") for _ in range(0,N+1)]
d[K] = 0
queue = []
queue.append((K,g[K],-1))
while queue:
    start,edge,parent = queue.pop(0)
    for to,cost in edge:
        if to == parent:
            continue
        if d[to] > d[start] + cost:
            d[to] = d[start] + cost
            queue.append((to,g[to],start))

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
g = [[] for _ in range(0,N+1)]
for i in range(0,N-1):
    a,b,c = map(int,input().split())
    g[a].append((b,c))
    g[b].append((a,c))
Q,K = map(int,input().split())
xy = []
for i in range(0,Q):
    x,y = map(int,input().split())
    xy.append((x,y))

#dijkstra
d = [float("inf") for _ in range(0,N+1)]
d[K] = 0
queue = []
queue.append((K,g[K]))
while queue:
    start,edge = queue.pop(0)
    for to,cost in edge:
        if d[to] > d[start] + cost:
            d[to] = d[start] + cost
            queue.append((to,g[to]))

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

Submission status: Time Limit Exceeded

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():
            if j not in checked:
                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: Time Limit Exceeded

Solution code:
import queue

def ans():
    def dfs(v, p, d):
        visited = []
        q = queue.Queue()
        for i in tree[v]:
            q.put((i[0], i[1], p))
        visited.append(v)
        while not q.empty():
            e, cost, parent = q.get()
            if (e in visited): continue
            if e == parent : continue
            visited.append(e)
            depth[e] = cost
            for i in tree[e]:
                if (i[0] in visited): continue
                q.put((i[0], i[1] + cost, e))

    n = int(input())
    tree = [[] for _ in range(n+1)]
    depth = [0] * (n * 2)
    for _ in range(1,n):
        a, b, c = map(int, input().split())
        tree[a].append((b,c))
        tree[b].append((a,c))

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

ans()

Submission status: Time Limit Exceeded

Solution code:
import queue
MAX = 10 ** 10
def m():
    def dijkstra(ds, start):
        q = queue.PriorityQueue()
        visited = []
        for to, cost in graph[start]:
            q.put((cost, to))
        visited.append(start)
        while not q.empty():
            cost, to = q.get()
            if to in visited: continue
            if cost == MAX: continue
            visited.append(to)
            ds[start][to] = cost
            for k, cost in graph[to]:
                if (k in visited) == False:
                    q.put((cost + ds[start][to], k))
        return ds

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

    q, k = map(int, input().split())
    ds = [[MAX for _ in range(n+1)] for _ in range(n+1)]
    for i in range(n+1): ds[i][i] = 0
    ds = dijkstra(ds, k)
    for _ in range(q):
        x, y = map(int, input().split())
        ds = dijkstra(ds, x)
        print(ds[x][k] + ds[k][y])

m()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
branch = dict()
for i in range(1,n+1):
	branch[i] = []
for i in range(n-1):
	a,b,c = map(int,input().split())
	branch[a].append([b,c])
	branch[b].append([a,c])
cumsum = [0 for i in range(n+1)]
q,k = map(int,input().split())
cumsum[k] = 1
queue = [k]
while len(queue) > 0:
	for i in range(len(branch[queue[0]])):
		if cumsum[branch[queue[0]][i][0]] == 0:
			cumsum[branch[queue[0]][i][0]] = cumsum[queue[0]] + branch[queue[0]][i][1]
			queue.append(branch[queue[0]][i][0])
	queue.pop(0)

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
branch = dict()
for i in range(1,n+1):
	branch[i] = []
for i in range(n-1):
	a,b,c = map(int,input().split())
	branch[a].append([b,c])
	branch[b].append([a,c])
cumsum = [0 for i in range(n+1)]
q,k = map(int,input().split())
cumsum[k] = 1
queue = [k]
while len(queue) > 0:
	for i in range(len(branch[queue[0]])):
		if cumsum[branch[queue[0]][i][0]] == 0:
			cumsum[branch[queue[0]][i][0]] = cumsum[queue[0]] + branch[queue[0]][i][1]
			queue.append(branch[queue[0]][i][0])
	queue.pop(0)

ans = []
for i in range(q):
	x,y = map(int,input().split())
	ans.append(cumsum[x]+cumsum[y]-2)
for i in range(q):
	print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
a=[0 for i in range(N-1)]
b=[0 for i in range(N-1)]
c=[0 for i in range(N-1)]
G=[[0 for i in range(N)] for i in range(N)]
VL=[set() for i in range(N)]
for i in range(N-1):
    a[i],b[i],c[i]=map(int,input().split())
    a[i]-=1
    b[i]-=1
    G[a[i]][b[i]]+=c[i]
    G[b[i]][a[i]]+=c[i]
    VL[a[i]].add(b[i])
    VL[b[i]].add(a[i])
Q,K=map(int,input().split())
K-=1
x=[0 for i in range(Q)]
y=[0 for i in range(Q)]
for i in range(Q):
    x[i],y[i]=map(int,input().split())
    x[i]-=1
    y[i]-=1
reached=[False for i in range(N)]
dist=[0 for i in range(N)]
def dfs(v):
    reached[v]=True
    for u in VL[v]:
        if not(reached[u]):
            dist[u]=dist[v]+G[u][v]
            dfs(u)
dfs(K)
for i in range(Q):
    print(dist[x[i]]+dist[y[i]])

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
a=[0 for i in range(N-1)]
b=[0 for i in range(N-1)]
c=[0 for i in range(N-1)]
G=[[0 for i in range(N)] for i in range(N)]
VL=[set() for i in range(N)]
for i in range(N-1):
    a[i],b[i],c[i]=map(int,input().split())
    a[i]-=1
    b[i]-=1
    G[a[i]][b[i]]+=c[i]
    G[b[i]][a[i]]+=c[i]
    VL[a[i]].add(b[i])
    VL[b[i]].add(a[i])
Q,K=map(int,input().split())
K-=1
x=[0 for i in range(Q)]
y=[0 for i in range(Q)]
for i in range(Q):
    x[i],y[i]=map(int,input().split())
    x[i]-=1
    y[i]-=1
d=[10**15 for i in range(N)]
d[K]=0
V=set(range(N))
while(len(V)>0):
    u=list(V)[0]
    for v in V:
        if d[u]>d[v]:
            u=v
    V-=set([u])
    for v in VL[u]:
        if d[v]>d[u]+G[u][v]:
            d[v]=d[u]+G[u][v]
for i in range(Q):
    print(d[x[i]]+d[y[i]])

Submission status: Time Limit Exceeded

Solution code:
import heapq
n = int(input())
cost = [[float('inf') for _ in range(n+1)] for _ in range(n+1)]
for _ in range(n-1):
    From, To, d = map(int, input().split())
    cost[From][To] = d
    cost[To][From] = d

q, k = map(int, input().split())
dist = [float('inf') for _ in range(n+1)]
dist[k] = 0
next_v = [[0, k]]

while len(next_v):
    v = next_v[0][1]
    for i in range(n+1):
        if dist[i] > dist[v] + cost[v][i]:
            dist[i] = dist[v] + cost[v][i]
            heapq.heappush(next_v, [dist[i], i])
    heapq.heappop(next_v)

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

Submission status: Time Limit Exceeded

Solution code:
import heapq
n = int(input())
cost = [[float('inf') for _ in range(n+1)] for _ in range(n+1)]
for _ in range(n-1):
    From, To, d = map(int, input().split())
    cost[From][To] = d
    cost[To][From] = d

q, k = map(int, input().split())
dist = [[float('inf') for _ in range(n+1)] for _ in range(n+1)]
used = [False]*(n+1)

for i in range(n+1):
    dist[i][i] = 0
        
def dijkstra(s, dist):
    next_v = [[0, s]]
    
    while len(next_v):
        v = next_v[0][1]
        for i in range(n+1):
            if dist[s][i] > dist[s][v] + cost[v][i]:
                dist[s][i] = dist[s][v] + cost[v][i]
                heapq.heappush(next_v, [dist[s][i], i])
        heapq.heappop(next_v)
        
    return dist

dist = dijkstra(k, dist)

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

Submission status: Time Limit Exceeded

Solution code:
import heapq
n = int(input())
cost = [[float('inf') for _ in range(n+1)] for _ in range(n+1)]
for _ in range(n-1):
    From, To, d = map(int, input().split())
    cost[From][To] = d
    cost[To][From] = d

q, k = map(int, input().split())
dist = [[float('inf') for _ in range(n+1)] for _ in range(n+1)]
used = [False]*(n+1)

for i in range(n+1):
    dist[i][i] = 0
        
def dijkstra(s, dist):
    next_v = [[0, s]]
    
    while len(next_v):
        v = next_v[0][1]
        for i in range(n+1):
            if dist[s][i] > dist[s][v] + cost[v][i]:
                dist[s][i] = dist[s][v] + cost[v][i]
                heapq.heappush(next_v, [dist[s][i], i])
        heapq.heappop(next_v)
        
    return dist
dist = dijkstra(k, dist)

for _ in range(q):
    x, y = map(int, input().split())
    if used[x] == False:
        dist = dijkstra(x, dist)
        used[x] = True
    print(dist[x][k]+dist[k][y])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [[int(i) for i in input().split()] for i in range(n-1)]
q,k = (int(i) for i in input().split())
question = [[int(i) for i in input().split()] for i in range(q)]
x = []
for i in range(n):
	subx = []
	for j in range(n):
		subx.append(float("inf"))
	x.append(subx)
for i in range(n): x[i][i] = 0
for i in a: x[i[0]-1][i[1]-1],x[i[1]-1][i[0]-1] = i[2],i[2]
for p in range(n):
	for i in range(n):
		for j in range(n):
			x[i][j] = min(x[i][p]+x[p][j],x[i][j])
for i in question:
	print(x[i[0]-1][k-1]+x[k-1][i[1]-1])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
edges = [[] for i in range(N-1)]
for i in range(N-1):
    edges[i]=list(map(int, input().split()))

##print('edges=',edges)
def connected(v):
    children = []
    for edge in edges:
        if edge[0] == v:
            children.append([edge[1],edge[2]])
        elif edge[1] == v:
            children.append([edge[0],edge[2]])

    return children

Q,K = map(int, input().split())
##print('Q=',Q)
depth = [0]*(N+1)
def DFS(v, p, d):
    depth[v] = d
    for child in connected(v):
        if child[0] == p:
            continue
        DFS(child[0], v, d+child[1])

DFS(K,-1,0)
for i in range(Q):
    xi, yi = map(int, input().split())
    print(depth[xi]+depth[yi])

Submission status: Time Limit Exceeded

Solution code:
import heapq

N=int(input())
C=[[float('inf') for x in range(N)] for y in range(N)]
for i in range(N-1):
  a,b,c=map(int,input().split())
  C[a-1][b-1]=c
  C[b-1][a-1]=c
Q,K=map(int,input().split())
d=[float('inf') for j in range(N)]
d[K-1]=0
q=[]

heapq.heappush(q, (0, K-1))
while len(q) != 0:
  prov_cost, src = heapq.heappop(q)
  if d[src] < prov_cost:
    continue
  for dest in range(N):
    cost = C[src][dest]
    if cost != float('inf') and d[dest] > d[src] + cost:
      d[dest] = d[src] + cost
      heapq.heappush(q, (d[dest], dest))

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:
N=int(input())
C=[[1000000000000 for x in range(N)] for y in range(N)]
for i in range(N-1):
  a,b,c=map(int,input().split())
  C[a-1][b-1]=c
  C[b-1][a-1]=c
Q,K=map(int,input().split())
d=[1000000000000 for j in range(N)]
use=[0 for i in range(N)]
d[K-1]=0
while True:
  v=-1
  for i in range(N):
    if use[i]==0 and (v==-1 or d[i]<d[v]):
      v=i
  if v==-1:
    break
  use[v]=1
  for j in range(N):
    d[j]=min(d[j],d[v]+C[v][j])

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:
import sys
#sys.stdin = open('Transit_Tree_Path.txt', 'r')

def dfs(g, start):
    dist = [-1 for i in xrange(len(g))]
    dist[start] = 0

    q = [start]
    while len(q) > 0:
        u = q.pop()
        for v, l in g[u].iteritems():
            if dist[v] == -1 or dist[u] + l < dist[v]:
                dist[v] = dist[u] + l
                if not v in q:
                    q.append(v)
                    
    return dist

n = int(raw_input())
g = [{} for i in xrange(n+1)]

for i in xrange(n-1):
    u, v, l = map(int, raw_input().split())
    g[u][v] = l
    g[v][u] = l


q, k = map(int, raw_input().split())
dist = dfs(g, k)
for i in xrange(q):
    x, y = map(int, raw_input().split())
    print dist[x] + dist[y]

Submission status: Time Limit Exceeded

Solution code:
import sys
#sys.stdin = open('Transit_Tree_Path.txt', 'r')

def spfa(g, start):
    dist = [1e15 for i in xrange(len(g))]
    dist[start] = 0

    q = [start]
    while len(q) > 0:
        u = q.pop(0)
        for v, l in g[u].iteritems():
            if dist[u] + l < dist[v]:
                dist[v] = dist[u] + l
                if not v in q:
                    q.append(v)
                    
    return dist

n = int(raw_input())
g = [{} for i in xrange(n+1)]

for i in xrange(n-1):
    u, v, l = map(int, raw_input().split())
    g[u][v] = l
    g[v][u] = l


q, k = map(int, raw_input().split())
dist = spfa(g, k)
for i in xrange(q):
    x, y = map(int, raw_input().split())
    print dist[x] + dist[y]

Submission status: Time Limit Exceeded

Solution code:
import sys
#sys.stdin = open('Transit_Tree_Path.txt', 'r')

def spfa(g, start, end):
    dist = [1e15 for i in xrange(len(g))]
    dist[start] = 0

    q = [start]
    while len(q) > 0:
        u = q.pop(0)
        for v, l in g[u].iteritems():
            if dist[u] + l < dist[v]:
                dist[v] = dist[u] + l
                if not v in q:
                    q.append(v)
                    
    return dist[end]

n = int(raw_input())
g = [{} for i in xrange(n+1)]

for i in xrange(n-1):
    u, v, l = map(int, raw_input().split())
    g[u][v] = l
    g[v][u] = l
    
q, k = map(int, raw_input().split())
for i in xrange(q):
    x, y = map(int, raw_input().split())
    print spfa(g, x, k) + spfa(g, k, y)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
http://abc070.contest.atcoder.jp/tasks/abc070_d
"""
# TLEするので、ダイクストラのアルゴリズムからの高速化が必要。
# 隣接行列をやめて隣接リストにしたところ、だいぶ速度が改善された。しかし、今度はWAが出るようになった。
# WAはコスト無限大の設定値が低すぎたため、経路コストがオーバーしてしまっていたため。float('inf')にして TLEのみになった
# d[]をnumpyの行列にしてみた → 遅くなっただけ
# クラスをやめてベタ書きに
from heapq import heappush, heappop


def solve(N, K, adj, queries):
    WHITE, GRAY, BLACK = 0, 1, 2

    num_of_nodes = N+1
    color = [WHITE] * num_of_nodes  # 各ノードの訪問状態
    d = [float('inf')] * num_of_nodes  # 始点からの重み

    # dijkstra(self, start):
    d[K] = 0
    pq = [(0, K)]

    while pq:
        cost, u = heappop(pq)
        color[u] = BLACK
        if d[u] < cost:
            continue

        for v, c in adj[u]:
            if color[v] == BLACK:
                continue
            if d[v] > d[u] + c:
                d[v] = d[u] + c
                heappush(pq, (d[v], v))
                color[v] = GRAY

    # 結果の表示
    for x, y in queries:
        print(d[x] + d[y])



def main():
    # データの入力
    N = int(input())
    adj = [[] for _ in range(N+1)]
    for i in range(N-1):
        f, t, c = [int(x) for x in input().split(' ')]
        adj[f].insert(0, (t, c))
        adj[t].insert(0, (f, c))

    queries = []
    Q, K = [int(x) for x in input().split(' ')]
    for i in range(Q):
        queries.append([int(x) for x in input().split(' ')])

    # 経路の探索
    solve(N, K, adj, queries)



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
http://abc070.contest.atcoder.jp/tasks/abc070_d
"""
# TLEするので、ダイクストラのアルゴリズムからの高速化が必要。
# 隣接行列をやめて隣接リストにしたところ、だいぶ速度が改善された。しかし、今度はWAが出るようになった。
# WAはコスト無限大の設定値が低すぎたため、経路コストがオーバーしてしまっていたため。float('inf')にして TLEのみになった
# d[]をnumpyの行列にしてみた → 遅くなっただけ
# クラスをやめてベタ書きに
from heapq import heappush, heappop


def solve(N, K, data):
    WHITE, GRAY, BLACK = 0, 1, 2

    num_of_nodes = N+1
    color = [WHITE] * num_of_nodes  # 各ノードの訪問状態
    d = [float('inf')] * num_of_nodes  # 始点からの重み
    adj = [[] for _ in range(num_of_nodes)]

    for f, t, c in data:
        adj[f].insert(0, (t, c))
        adj[t].insert(0, (f, c))


    # dijkstra(self, start):
    d[K] = 0
    pq = [(0, K)]

    while pq:
        cost, u = heappop(pq)
        color[u] = BLACK
        if d[u] < cost:
            continue

        for v, c in adj[u]:
            if color[v] == BLACK:
                continue
            if d[v] > d[u] + c:
                d[v] = d[u] + c
                heappush(pq, (d[v], v))
                color[v] = GRAY
    return d



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

    # 経路の探索
    d = solve(N, K, data)

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
http://abc070.contest.atcoder.jp/tasks/abc070_d
"""
# TLEするので、ダイクストラのアルゴリズムからの高速化が必要。
# 隣接行列をやめて隣接リストにしたところ、だいぶ速度が改善された。しかし、今度はWAが出るようになった。
# WAはコスト無限大の設定値が低すぎたため、経路コストがオーバーしてしまっていたため。float('inf')にして TLEのみになった
# d[]をnumpyの行列にしてみた → 遅くなっただけ

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))
        remaining = len(self.d) - 1

        while pq and remaining:
            cost, u = heappop(pq)
            self.color[u] = Sssp.Status.black
            remaining -= 1
            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:
# -*- coding: utf-8 -*-
"""
http://abc070.contest.atcoder.jp/tasks/abc070_d
"""
# TLEするので、ダイクストラのアルゴリズムからの高速化が必要。
# 隣接行列をやめて隣接リストにしたところ、だいぶ速度が改善された。しかし、今度はWAが出るようになった。
# WAはコスト無限大の設定値が低すぎたため、経路コストがオーバーしてしまっていたため。float('inf')にして TLEのみになった

from enum import Enum
from heapq import heappush, heappop
import numpy as np


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.d = np.array([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(int(s.d[q[0]] + s.d[q[1]]))



if __name__ == '__main__':
    main()