Problem:


Score : 500 points

Problem Statement

There are N towns numbered 1 to N and M roads. The i-th road connects Town A_i and Town B_i bidirectionally and has a length of C_i.

Takahashi will travel between these towns by car, passing through these roads. The fuel tank of his car can contain at most L liters of fuel, and one liter of fuel is consumed for each unit distance traveled. When visiting a town while traveling, he can full the tank (or choose not to do so). Travel that results in the tank becoming empty halfway on the road cannot be done.

Process the following Q queries:

The tank is now full. Find the minimum number of times he needs to full his tank while traveling from Town s_i to Town t_i. If Town t_i is unreachable, print -1.

Constraints

All values in input are integers.

2 \leq N \leq 300

0 \leq M \leq \frac{N(N-1)}{2}

1 \leq L \leq 10^9

1 \leq A_i, B_i \leq N

A_i \neq B_i

\left(A_i, B_i\right) \neq \left(A_j, B_j\right) (if i \neq j)

\left(A_i, B_i\right) \neq \left(B_j, A_j\right) (if i \neq j)

1 \leq C_i \leq 10^9

1 \leq Q \leq N\left(N-1\right)

1 \leq s_i, t_i \leq N

s_i \neq t_i

\left(s_i, t_i\right) \neq \left(s_j, t_j\right) (if i \neq j)

Input

Input is given from Standard Input in the following format:

N M L
A_1 B_1 C_1
:
A_M B_M C_M
Q
s_1 t_1
:
s_Q t_Q

Output

Print Q lines.

The i-th line should contain the minimum number of times the tank needs to be fulled while traveling from Town s_i to Town t_i. If Town t_i is unreachable, the line should contain -1 instead.

Sample Input 1

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

Sample Output 1

0
1

To travel from Town 3 to Town 2, we can use the second road to reach Town 2 without fueling the tank on the way.

To travel from Town 1 to Town 3, we can first use the first road to get to Town 2, full the tank, and use the second road to reach Town 3.

Sample Input 2

4 0 1
1
2 1

Sample Output 2

-1

There may be no road at all.

Sample Input 3

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

Sample Output 3

0
0
1
2
0
0
1
2
0
0
0
1
1
1
0
0
2
2
1
0



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


Sample output:
0
1

Submission status: Time Limit Exceeded

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

import sys
from collections import deque
from array import array

def input():
    return sys.stdin.readline().rstrip('\n')

N,M,L = list(map(int, input().split()))

_C = {}

for i in range(M):
    a,b,c = list(map(int, input().split()))
    a -= 1
    b -= 1
    if c>L:
        continue
    _C[a*300+b] = c
    _C[b*300+a] = c

def C_(i,j):
    return _C.get(i*300+j, sys.maxsize)

Q = int(input())

#S = array('q', [0]*Q)
#T = array('q', [0]*Q)
S = [0]*Q
T = [0]*Q

for i in range(Q):
    S[i],T[i] = list(map(int, input().split()))

# ワーシャルフロイド法

# distance from i to j
#D = [array('q', [0]*N) for i in range(N)]
D = [[0]*N for i in range(N)]

# initialization
for i in range(N):
    for j in range(N):
        D[i][j] = C_(i,j)
        #print(i,j,D[i][j])

# 本計算
for k in range(N):
    Dk = D[k]
    for i in range(N):
        Di = D[i]
        for j in range(N):
            #if D[i][j] > D[i][k] + D[k][j]:
                #D[i][j] = D[i][k] + D[k][j]
            if Di[j] > Di[k] + Dk[j]:
                Di[j] = Di[k] + Dk[j]


# D[i][j] <= L となる i,j に辺を張る
for i in range(N):
    for j in range(N):
        if D[i][j] <= L:
            _C[i*300+j] = 1
            _C[j*300+i] = 1

# ワーシャルフロイド法 again

# distance from i to j
#D = [array('q', [0]*N) for i in range(N)]
D = [[0]*N for i in range(N)]
#STEP = [array('q', [0]*N) for i in range(N)]
STEP = [[0]*N for i in range(N)]

# initialization
for i in range(N):
    for j in range(N):
        c = C_(i,j)
        D[i][j] = c
        if c == sys.maxsize:
            STEP[i][j] = sys.maxsize
        else:
            STEP[i][j] = 1
        #print(i,j,D[i][j],STEP[i][j])

# 本計算
for k in range(N):
    Dk = D[k]
    STEPk = STEP[k]
    for i in range(N):
        Di = D[i]
        STEPi = STEP[i]
        for j in range(N):
            if Di[j] > Di[k] + Dk[j]:
                Di[j] = Di[k] + Dk[j]
                STEPi[j] = STEPi[k] + STEPk[j]


# answer
for q in range(Q):
    i = S[q]-1
    j = T[q]-1
    step = STEP[i][j]
    if step == sys.maxsize:
        #print(i,j,-1)
        print(-1)
    else:
        print(step-1)

Submission status: Time Limit Exceeded

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

import sys
from collections import deque
from array import array

def input():
    return sys.stdin.readline().rstrip('\n')

N,M,L = list(map(int, input().split()))

_C = {}

for i in range(M):
    a,b,c = list(map(int, input().split()))
    a -= 1
    b -= 1
    if c>L:
        continue
    _C[a*300+b] = c
    _C[b*300+a] = c

def C_(i,j):
    return _C.get(i*300+j, sys.maxsize)

Q = int(input())

#S = array('q', [0]*Q)
#T = array('q', [0]*Q)
S = [0]*Q
T = [0]*Q

for i in range(Q):
    S[i],T[i] = list(map(int, input().split()))

# ワーシャルフロイド法

# distance from i to j
#D = [array('q', [0]*N) for i in range(N)]
D = [[0]*N for i in range(N)]

# initialization
for i in range(N):
    for j in range(N):
        D[i][j] = C_(i,j)
        #print(i,j,D[i][j])

# 本計算
for k in range(N):
    for i in range(N):
        for j in range(N):
            if D[i][j] > D[i][k] + D[k][j]:
                D[i][j] = D[i][k] + D[k][j]


# D[i][j] <= L となる i,j に辺を張る
for i in range(N):
    for j in range(N):
        if D[i][j] <= L:
            _C[i*300+j] = 1
            _C[j*300+i] = 1

# ワーシャルフロイド法 again

# distance from i to j
#D = [array('q', [0]*N) for i in range(N)]
D = [[0]*N for i in range(N)]
#STEP = [array('q', [0]*N) for i in range(N)]
STEP = [[0]*N for i in range(N)]

# initialization
for i in range(N):
    for j in range(N):
        c = C_(i,j)
        D[i][j] = c
        if c == sys.maxsize:
            STEP[i][j] = sys.maxsize
        else:
            STEP[i][j] = 1
        #print(i,j,D[i][j],STEP[i][j])

# 本計算
for k in range(N):
    for i in range(N):
        for j in range(N):
            if D[i][j] > D[i][k] + D[k][j]:
                D[i][j] = D[i][k] + D[k][j]
                STEP[i][j] = STEP[i][k] + STEP[k][j]


# answer
for q in range(Q):
    i = S[q]-1
    j = T[q]-1
    step = STEP[i][j]
    if step == sys.maxsize:
        #print(i,j,-1)
        print(-1)
    else:
        print(step-1)

Submission status: Time Limit Exceeded

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

import sys
from collections import deque
from array import array

def input():
    return sys.stdin.readline().rstrip('\n')

N,M,L = list(map(int, input().split()))

_C = {}

for i in range(M):
    a,b,c = list(map(int, input().split()))
    a -= 1
    b -= 1
    if c>L:
        continue
    _C[a*300+b] = c
    _C[b*300+a] = c

def C_(i,j):
    return _C.get(i*300+j, sys.maxsize)

Q = int(input())

S = array('q', [0]*Q)
T = array('q', [0]*Q)

for i in range(Q):
    S[i],T[i] = list(map(int, input().split()))

# ワーシャルフロイド法

# distance from i to j
D = [array('q', [0]*N) for i in range(N)]

# initialization
for i in range(N):
    for j in range(N):
        D[i][j] = C_(i,j)
        #print(i,j,D[i][j])

# 本計算
for k in range(N):
    for i in range(N):
        for j in range(N):
            if D[i][j] > D[i][k] + D[k][j]:
                D[i][j] = D[i][k] + D[k][j]


# D[i][j] <= L となる i,j に辺を張る
for i in range(N):
    for j in range(N):
        if D[i][j] <= L:
            _C[i*300+j] = 1
            _C[j*300+i] = 1

# ワーシャルフロイド法 again

# distance from i to j
D = [array('q', [0]*N) for i in range(N)]
STEP = [array('q', [0]*N) for i in range(N)]

# initialization
for i in range(N):
    for j in range(N):
        c = C_(i,j)
        D[i][j] = c
        if c == sys.maxsize:
            STEP[i][j] = sys.maxsize
        else:
            STEP[i][j] = 1
        #print(i,j,D[i][j],STEP[i][j])

# 本計算
for k in range(N):
    for i in range(N):
        for j in range(N):
            if D[i][j] > D[i][k] + D[k][j]:
                D[i][j] = D[i][k] + D[k][j]
                STEP[i][j] = STEP[i][k] + STEP[k][j]


# answer
for q in range(Q):
    i = S[q]-1
    j = T[q]-1
    step = STEP[i][j]
    if step == sys.maxsize:
        #print(i,j,-1)
        print(-1)
    else:
        print(step-1)

Submission status: Time Limit Exceeded

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

def main():
    N,M,L = map(int,input().split())
    edge = [[float("inf") for _ in range(N)] for _ in range(N)]
    
    for _ in range(M):
        a,b,c = map(int,input().split())
        edge[a-1][b-1] = edge[b-1][a-1] = c
    
    for i in range(N):
        edge[i][i] = 0

    for i in range(N):
        for j in range(N):
            for k in range(N):
                if (edge[j][k] > edge[j][i]+edge[i][k]):
                    edge[j][k] = edge[j][i]+edge[i][k]
    
    ref = [[float("inf") for _ in range(N)] for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if edge[i][j] <= L:
                ref[i][j] = 1
            
    for i in range(N):
        for j in range(N):
            for k in range(N):
                if (ref[j][k] > ref[j][i]+ref[i][k]):
                    ref[j][k] = ref[j][i]+ref[i][k]

    Q = int(input())
    for _ in range(Q):
        a,b = map(int,input().split())
        print(ref[a-1][b-1]-1 if ref[a-1][b-1] != float("inf") else -1)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N, M, L = (int(i) for i in input().split())

import heapq
def Dijkstra(graph, start):
    N = len(graph)
    d = {}
    prev = {}
    for i in range(N):
        prev[i] = None
        if i == start:
            d[i] = 0
        else:
            d[i] = float('inf')
    Q = []
    heapq.heappush(Q, (0, start))
    while Q:
        d_u, u = heapq.heappop(Q)
        if d[u] < d_u:#ダブりを回避
            continue
        for i in range(N):
            if graph[u][i]:
                temp = d_u + graph[u][i]
                if d[i] > temp:
                    d[i] = temp
                    prev[i] = u
                    heapq.heappush(Q, (d[i], i))
    return (d, prev)

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

new_graph = [[0]*N for i in range(N)]
for i in range(N):
    d, prev = Dijkstra(graph, i)
    for j in range(N):
        if d[j] <= L:
            new_graph[i][j] = 1
            new_graph[j][i] = 1

ans = []
for i in range(N):
    d, prev = Dijkstra(new_graph, i)
    ans.append(d)

Q = int(input())
for i in range(Q):
    s, t = (int(i) for i in input().split())
    if ans[s-1][t-1] == float("inf"):
        print("-1")
    else:
        print(ans[s-1][t-1]-1)

Submission status: Time Limit Exceeded

Solution code:
import heapq

n, m, l = map(int, input().split())
v = [[] for i in range(n)]
for i in range(m):
    a, b, c, = map(int, input().split())
    a, b, = a-1, b-1
    if c > l:
        continue
    v[a].append((c, b))
    v[b].append((c, a))


def dijkstra(home):
    visited = [False for i in range(n)]
    visited[home] = -1
    queue = []
    for edge in v[home]:
        heapq.heappush(queue, edge)


    while queue:
        value, x = heapq.heappop(queue)
        if visited[x]:
            continue
        visited[x] = value
        for new_value, new_x in v[x]:
            if not visited[new_x]:
                heapq.heappush(queue, new_value+value)

    return visited


def dijkstra2(home):
    visited = [None for _ in range(n)]
    visited[home] = 0
    queue = []
    for fuel_needed, x in v[home]:
        heapq.heappush(queue, (0, fuel_needed, x))


    while queue:
        tanked, fuel_needed, x = heapq.heappop(queue)
        fuel = l-fuel_needed
        if visited[x] is not None:
            continue
        visited[x] = tanked
        for child_value, child_x in v[x]:
            if visited[child_x] is None:
                if child_value > fuel:
                    heapq.heappush(queue, (tanked+1, child_value, child_x))
                else:
                    heapq.heappush(queue, (tanked, fuel_needed+child_value, child_x))

    return visited






visited_collection = [None for _ in range(n)]



q = int(input())
queries = []
for i in range(q):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    if visited_collection[a]:
        print(visited_collection[a][b] if visited_collection[a][b] is not None else -1)
    elif visited_collection[b]:
        print(visited_collection[b][a] if visited_collection[b][a] is not None else -1)
    else:
        visited_collection[a] = dijkstra2(a)
        print(visited_collection[a][b] if visited_collection[a][b] is not None else -1)

    # queries.append((a, b))

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, M, L = map(int, input().split())
    dist = [[float('inf')] * N for _ in range(N)]
    for _ in range(M):
        A, B, C = map(int, input().split())
        if C > L:
            continue
        A -= 1
        B -= 1
        dist[A][B] = C
        dist[B][A] = C

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

    e = [[float('inf')] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if dist[i][j] <= L:
                e[i][j] = 1
    
    for k in range(N):
        for i in range(N):
            for j in range(N):
                e[i][j] = min(e[i][j], e[i][k] + e[k][j])


    Q = int(input())
    for _ in range(Q):
        s, t = map(int, input().split())
        s -= 1
        t -= 1
        if e[s][t] == float('inf'):
            print(-1)
            continue
        ans = e[s][t]
        print(ans-1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

N, M, L = map(int, input().split())
inf = 10**15
d = [[] for _ in range(N)]

for _ in range(M):
    A, B, C = map(int, input().split())
    if C>L:continue
    d[A-1].append((B-1, C))
    d[B-1].append((A-1, C))

dists = []
for j in range(N):
    dist = [(inf,inf)]*N
    dist[j] = (0, 0)
    q = [(0, 0, j)]
    while q:
        charged, used, u = heappop(q)
        if (charged, used) > dist[u]:
            continue
        for v, next_cost in d[u]:
            if v==u:
                continue
            c = (charged+1, next_cost) if used+next_cost>L else (charged, used+next_cost)
            if dist[v] > c:
                dist[v] = c
                heappush(q, c+(v,))
    dists.append(dist)

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    ans = dists[s-1][t-1][0]
    print(ans if ans!=inf else -1)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

N, M, L = map(int, input().split())
inf = 10**15
d = [[] for _ in range(N)]

for _ in range(M):
    A, B, C = map(int, input().split())
    if C>L:continue
    d[A-1].append((B-1, C))
    d[B-1].append((A-1, C))

dists = []
for j in range(N):
    dist = [(inf,inf)]*N
    dist[j] = (0, 0)
    q = [(0, 0, j)]
    while q:
        charged, used, u = heappop(q)
        if (charged, used) > dist[u]:
            continue
        for v, next_cost in d[u]:
            c = (charged+1, next_cost) if used+next_cost>L else (charged, used+next_cost)
            if dist[v] > c:
                dist[v] = c
                heappush(q, c+(v,))
    dists.append(dist)

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    ans = dists[s-1][t-1][0]
    print(ans if ans!=inf else -1)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

N, M, L = map(int, input().split())
inf = 10**15
d = [[] for _ in range(N)]

for _ in range(M):
    A, B, C = map(int, input().split())
    if C>L:continue
    d[A-1].append((B-1, C))
    d[B-1].append((A-1, C))

dists = []
for j in range(N):
    dist = [(inf,inf)]*N
    dist[j] = (0, 0)
    q = [(0, 0, j)]
    while q:
        charged, used, u = heappop(q)
        if (charged, used) > dist[u]:
            continue
        for v, next_cost in d[u]:
            c = (charged+1, next_cost) if used+next_cost>L else (charged, used+next_cost)
            if dist[v] > c:
                dist[v] = c
                heappush(q, c+(v,))
    dists.append(dist)

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    ans = dists[s-1][t-1][0]
    print(ans if ans!=inf else -1)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
from collections import defaultdict
import sys
input = sys.stdin.readline

N, M, L = map(int, input().split())
inf = 10**15
d = defaultdict(list)

for _ in range(M):
    A, B, C = map(int, input().split())
    if C>L:continue
    d[A-1].append((B-1, C))
    d[B-1].append((A-1, C))

dists = []
for j in range(N):
    dist = [(inf,inf)]*N
    dist[j] = (0, 0)
    q = [(0, 0, j)]
    while q:
        charged, used, u = heappop(q)
        if (charged, used) > dist[u]:
            continue
        for v, next_cost in d[u]:
            c = (charged+1, next_cost) if used+next_cost>L else (charged, used+next_cost)
            if dist[v] > c:
                dist[v] = c
                heappush(q, c+(v,))
    dists.append(dist)

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    ans = dists[s-1][t-1][0]
    print(ans if ans!=inf else -1)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
from collections import defaultdict
import sys
input = sys.stdin.readline

N, M, L = map(int, input().split())
inf = 10**15
d = defaultdict(list)

for _ in range(M):
    A, B, C = map(int, input().split())
    if C>L:continue
    d[A-1].append((B-1, C))
    d[B-1].append((A-1, C))

charged_dict = [[(inf,inf)]*N for _ in range(N)]
for j in range(N):
    charged_dict[j][j] = (0, 0)
    q = [(0, 0, j)]
    while q:
        charged, used, u = heappop(q)
        if (charged, used) > charged_dict[j][u]:
            continue
        for v, next_cost in d[u]:
            c = (charged+1, next_cost) if used+next_cost>L else (charged, used+next_cost)
            if charged_dict[j][v] > c:
                charged_dict[j][v] = c
                heappush(q, c+(v,))

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    ans = charged_dict[s-1][t-1][0]
    print(ans if ans!=inf else -1)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
from collections import defaultdict
import sys
input = sys.stdin.readline

N, M, L = map(int, input().split())
inf = float("inf")
d = defaultdict(list)

for _ in range(M):
    A, B, C = map(int, input().split())
    if C>L:continue
    d[A-1].append((B-1, C))
    d[B-1].append((A-1, C))

charged_dict = [[(inf,inf)]*N for _ in range(N)]
for j in range(N):
    charged_dict[j][j] = (0, 0)
    q = [(0, 0, j)]
    while q:
        charged, used, u = heappop(q)
        if (charged, used) > charged_dict[j][u]:
            continue
        for v, next_cost in d[u]:
            c = (charged+1, next_cost) if used+next_cost>L else (charged, used+next_cost)
            if charged_dict[j][v] > c:
                charged_dict[j][v] = c
                heappush(q, c+(v,))

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    ans = charged_dict[s-1][t-1][0]
    print(ans if ans!=inf else -1)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
from collections import defaultdict
import sys
input = sys.stdin.readline

N, M, L = map(int, input().split())
inf = float("inf")
d = defaultdict(list)

for _ in range(M):
    A, B, C = map(int, input().split())
    if C>L:continue
    d[A-1].append((B-1, C))
    d[B-1].append((A-1, C))

charged_dict = [[(inf,inf)]*N for _ in range(N)]
for j in range(N):
    charged_dict[j][j] = (0, 0)
    q = [(0, 0, j)]
    while q:
        charged, used, u = heappop(q)
        for v, next_cost in d[u]:
            c = (charged+1, next_cost) if used+next_cost>L else (charged, used+next_cost)
            if charged_dict[j][v] > c:
                charged_dict[j][v] = c
                heappush(q, c+(v,))

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    ans = charged_dict[s-1][t-1][0]
    print(ans if ans!=inf else -1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())

def dijkstra(s,n,g):
    que = []
    d = [10**15 for _ in range(n)]
    d[s] = 0
    heappush( que,(0,s) )
    while que:
        p = heappop(que)
        v = p[1]
        if d[v] < p[0]:
            continue
        for i in range(len(g[v])):
            edge = g[v][i]
            if d[edge[0]] > d[v] + edge[1]:
                d[edge[0]] = d[v] + edge[1]
                heappush( que,(d[edge[0]] , edge[0]) )
    return d

def warshall_floyd(d,n):
    for i in range(n):
        d[i][i] = 0
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

def main():
    n,w,l = inpm()
    g = [[] for _ in range(n)]
    for _ in range(w):
        x,y,z = inpm()
        x -= 1
        y -= 1
        if z > l:
            continue
        g[x].append((y,z))
        g[y].append((x,z))
    q = inp()
    st = []
    for _ in range(q):
        s,t = inpm()
        s -= 1
        t -= 1
        st.append((s,t))
    d = [[] for _ in range(n)]
    for i in range(n):
        d[i] = dijkstra(i,n,g)
    G = [[10**15 for _ in range(n)] for _ in range(n)]
    for i in range(n-1):
        for j in range(i+1,n):
            if d[i][j] <= l:
                G[i][j] = 1
                G[j][i] = 1
    D = warshall_floyd(G,n)
    for i in range(q):
        [s,t] = st[i]
        ans = D[s][t]
        if ans == 10**15:
            print(-1)
            continue
        print(ans-1)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

N, M, L = map(int,input().split())
rd = [[] for _ in range(N+1)]
rc = [[] for _ in range(N+1)]

ZO = [[-1 for i in range(N+1)] for i in range(N+1)]
NP = [[10**9+1 for i in range(N+1)] for i in range(N+1)]

for _ in range(M):
    a,b,c = map(int,input().split())
    if c <= L:
        rd[a].append(b)
        rc[a].append(c)
        rd[b].append(a)
        rc[b].append(c)
        NP[a][b] = 0
        NP[b][a] = 0
        ZO[a][b] = L - c
        ZO[b][a] = L - c

Q = int(input())
S = []
T = []
for _ in range(Q):
    s,t = map(int,input().split())
    S.append(s)
    T.append(t)

for i in range(1,N+1):
    up = True
    while up:
        up = False
        for j in range(1,N+1):
            if ZO[i][j] < 0: continue
            for d,c in zip(rd[j], rc[j]):
                if d == i: continue
                if ZO[i][j] < c:
                    nnp = NP[i][j] + 1
                    nzo = L - c
                else:
                    nnp = NP[i][j]
                    nzo = ZO[i][j] - c
                if NP[i][d] > nnp or NP[i][d] == nnp and ZO[i][d] < nzo:
                    ZO[i][d] = nzo
                    NP[i][d] = nnp
                    up = True

for i in range(Q):
    if NP[S[i]][T[i]] > 10**9:
        print (-1)
    else:
        print(NP[S[i]][T[i]])

Submission status: Time Limit Exceeded

Solution code:
N, M, L = map(int,input().split())
rd = [[] for _ in range(N+1)]
rc = [[] for _ in range(N+1)]

ZO = [[-1 for i in range(N+1)] for i in range(N+1)]
NP = [[10**9+1 for i in range(N+1)] for i in range(N+1)]

for _ in range(M):
    a,b,c = map(int,input().split())
    if c <= L:
        rd[a].append(b)
        rc[a].append(c)
        rd[b].append(a)
        rc[b].append(c)
        NP[a][b] = 0
        NP[b][a] = 0
        ZO[a][b] = L - c
        ZO[b][a] = L - c

Q = int(input())
S = []
T = []
for _ in range(Q):
    s,t = map(int,input().split())
    S.append(s)
    T.append(t)

for i in range(1,N+1):
    up = True
    while up:
        up = False
        for j in range(1,N+1):
            if ZO[i][j] < 0: continue
            for d,c in zip(rd[j], rc[j]):
                if d == i: continue
                if ZO[i][j] < c:
                    nnp = NP[i][j] + 1
                    nzo = L - c
                else:
                    nnp = NP[i][j]
                    nzo = ZO[i][j] - c
                if NP[i][d] > nnp or NP[i][d] == nnp and ZO[i][d] < nzo:
                    ZO[i][d] = nzo
                    NP[i][d] = nnp
                    up = True

for i in range(Q):
    if NP[S[i]][T[i]] > 10**9:
        print (-1)
    else:
        print(NP[S[i]][T[i]])

Submission status: Time Limit Exceeded

Solution code:
N, M, L = map(int,input().split())
rd = [[] for _ in range(N+1)]
rc = [[] for _ in range(N+1)]

ZO = [[-1 for i in range(N+1)] for i in range(N+1)]
NP = [[10**9+1 for i in range(N+1)] for i in range(N+1)]

for _ in range(M):
    a,b,c = map(int,input().split())
    if c <= L:
        rd[a].append(b)
        rc[a].append(c)
        rd[b].append(a)
        rc[b].append(c)
        NP[a][b] = 0
        NP[b][a] = 0
        ZO[a][b] = L - c
        ZO[b][a] = L - c

Q = int(input())
S = []
T = []
for _ in range(Q):
    s,t = map(int,input().split())
    S.append(s)
    T.append(t)

for i in range(1,N+1):
    up = True
    while up:
        for j in range(1,N+1):
            if ZO[i][j] < 0: continue
            for d,c in zip(rd[j], rc[j]):
                if d == i: continue
                if ZO[i][j] < c:
                    nnp = NP[i][j] + 1
                    nzo = L - c
                else:
                    nnp = NP[i][j]
                    nzo = ZO[i][j] - c
                if NP[i][d] > nnp or NP[i][d] == nnp and ZO[i][d] < nzo:
                    ZO[i][d] = nzo
                    NP[i][d] = nnp
                    up = True

for i in range(Q):
    if NP[S[i]][T[i]] > 10**9:
        print (-1)
    else:
        print(NP[S[i]][T[i]])

Submission status: Time Limit Exceeded

Solution code:
N, M, L = map(int,input().split())
rd = [[] for _ in range(N+1)]
rc = [[] for _ in range(N+1)]

ZO = [[-1 for i in range(N+1)] for i in range(N+1)]
NP = [[10**9+1 for i in range(N+1)] for i in range(N+1)]

for _ in range(M):
    a,b,c = map(int,input().split())
    if c <= L:
        rd[a].append(b)
        rc[a].append(c)
        rd[b].append(a)
        rc[b].append(c)
        NP[a][b] = 0
        NP[b][a] = 0
        ZO[a][b] = L - c
        ZO[b][a] = L - c

Q = int(input())
S = []
T = []
for _ in range(Q):
    s,t = map(int,input().split())
    S.append(s)
    T.append(t)

up = [False] + [True for _ in range(N)]
while up.count(True) > 0:
    for i in range(1,N+1):
        if up[i] == False : continue
        up[i] = False
        for j in range(1,N+1):
            if ZO[i][j] < 0: continue
            for d,c in zip(rd[j], rc[j]):
                if d == i: continue
                if ZO[i][j] < c:
                    nnp = NP[i][j] + 1
                    nzo = L - c
                else:
                    nnp = NP[i][j]
                    nzo = ZO[i][j] - c
                if NP[i][d] > nnp or NP[i][d] == nnp and ZO[i][d] < nzo:
                    ZO[i][d] = nzo
                    NP[i][d] = nnp
                    up[i] = True

for i in range(Q):
    if NP[S[i]][T[i]] > 10**9:
        print (-1)
    else:
        print(NP[S[i]][T[i]])

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())

def dijkstra(s,n,g):
    que = []
    d = [10**15 for _ in range(n)]
    d[s] = 0
    heappush( que,(0,s) )
    while que:
        p =  heappop(que)
        v = p[1]
        if d[v] < p[0]:
            continue
        for i in range(len(g[v])):
            edge = g[v][i]
            if d[edge[0]] > d[v] + edge[1]:
                d[edge[0]] = d[v] + edge[1]
                heappush( que,(d[edge[0]] , edge[0]) )
    return d

def main():
    n,w,l = inpm()
    g = [[] for _ in range(n)]
    for _ in range(w):
        x,y,z = inpm()
        x -= 1
        y -= 1
        if z > l:
            continue
        g[x].append((y,z))
        g[y].append((x,z))
    q = inp()
    st = []
    for _ in range(q):
        s,t = inpm()
        s -= 1
        t -= 1
        st.append((s,t))
    d = [[] for _ in range(n)]
    for i in range(n):
        d[i] = dijkstra(i,n,g)
    key = 1
    for i in range(q):
        [s,t] = st[i]
        if d[s][t] > l:
            key = 0
            break
    if key:
        for _ in range(q):
            print(0)
        return
    G = [[] for _ in range(n)]
    for i in range(n-1):
        for j in range(i+1,n):
            if d[i][j] <= l:
                G[i].append((j,1))
                G[j].append((i,1))
    d = [[] for _ in range(n)]
    for i in range(n):
        d[i] = dijkstra(i,n,G)
    for i in range(q):
        [s,t] = st[i]
        ans = d[s][t]
        if ans == 10**15:
            print(-1)
            continue
        print(ans-1)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N, M, L = map(int,input().split())
rd = [[] for _ in range(N+1)]
rc = [[] for _ in range(N+1)]

ZO = [[-1 for i in range(N+1)] for i in range(N+1)]
NP = [[10**9+1 for i in range(N+1)] for i in range(N+1)]

for _ in range(M):
    a,b,c = map(int,input().split())
    if c <= L:
        rd[a].append(b)
        rc[a].append(c)
        rd[b].append(a)
        rc[b].append(c)
        NP[a][b] = 0
        NP[b][a] = 0
        ZO[a][b] = L - c
        ZO[b][a] = L - c

Q = int(input())
S = []
T = []
for _ in range(Q):
    s,t = map(int,input().split())
    S.append(s)
    T.append(t)
    
up = True
while up:
    up = False
    for i in range(1,N+1):
        for j in range(1,N+1):
            if ZO[i][j] < 0: continue
            for d,c in zip(rd[j], rc[j]):
                if d == i: continue
                if ZO[i][j] < c:
                    nnp = NP[i][j] + 1
                    nzo = L - c
                else:
                    nnp = NP[i][j]
                    nzo = ZO[i][j] - c
                if NP[i][d] > nnp or NP[i][d] == nnp and ZO[i][d] < nzo:
                    ZO[i][d] = nzo
                    NP[i][d] = nnp
                    up = True
                    
for i in range(Q):
    if NP[S[i]][T[i]] > 10**9:
        print (-1)
    else:
        print(NP[S[i]][T[i]])