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:
INFTY = 10**12
def wf(H):
    d = [[INFTY for _ in range(N+1)] for _ in range(N+1)]
    for i in range(1,N+1):
        d[i][i] = 0
        if i in H:
            for x in H[i]:
                j,c = x[0],x[1]
                d[i][j] = c
    for k in range(1,N+1):
        for i in range(1,N+1):
            for j in range(1,N+1):
                d[i][j] = min(d[i][j],d[i][k]+d[k][j])
    return d
N,M,L = map(int,input().split())
G = {}
for _ in range(M):
    A,B,C = map(int,input().split())
    if A not in G:
        G[A] = []
    G[A].append((B,C))
    if B not in G:
        G[B] = []
    G[B].append((A,C))
d1 = wf(G)
F = {}
for i in range(1,N):
    for j in range(i+1,N+1):
        if d1[i][j]<=L:
            if i not in F:
                F[i] = []
            F[i].append((j,1))
            if j not in F:
                F[j] = []
            F[j].append((i,1))
d2 = wf(F)
Q = int(input())
for _ in range(Q):
    s,t = map(int,input().split())
    if d2[s][t]<INFTY:
        print(d2[s][t]-1)
    else:
        print(-1)

Submission status: Time Limit Exceeded

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


def main():
    N, M, L = map(int, input().split())
    graph = [[INF]*N for _ in range(N)]
    for _ in range(M):
        A, B, C = map(int, input().split())
        graph[A-1][B-1] = C
        graph[B-1][A-1] = C
    for i in range(N):
        graph[i][i] = 0
    for k in range(N):
        for i in range(N):
            if graph[i][k] == INF:
                continue
            for j in range(N):
                if graph[k][j] == INF:
                    continue
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
    newGraph = [[INF]*N for _ in range(N)]
    for i in range(N):
        newGraph[i][i] = 0
        for j in range(i+1, N):
            if graph[i][j] <= L:
                newGraph[i][j] = 1
                newGraph[j][i] = 1
    for k in range(N):
        for i in range(N):
            if newGraph[i][k] == INF:
                continue
            for j in range(N):
                if newGraph[k][j] == INF:
                    continue
                newGraph[i][j] = min(newGraph[i][j], newGraph[i][k] + newGraph[k][j])
    Q = int(input())
    for _ in range(Q):
        s, t = map(int, input().split())
        if newGraph[s-1][t-1] == INF:
            print(-1)
        else:
            print(newGraph[s-1][t-1]-1)


if __name__ == '__main__': main()

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse import*
f=csgraph.johnson
n,m,l,*t=map(int,open(0).read().split())
m*=3
for i in f(f(csr_matrix((t[2:m:3],(t[:m:3],t[1:m:3])),[n+1]*2),0)<=l)[t[m+1::2],t[m+2::2]]:print(min(n,i)%n-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))

class SegmentTree:
    def __init__(self, value=[], N=0, comp=lambda x,y: x<=y, reverse=False):
        M = max(len(value),N)
        N = 2**(len(bin(M))-3)
        if N < M: N *= 2
        self.N = N
        self.node = [0] * (2*N-1)
        for i in range(N):
            self.node[N-1+i] = i
        self.value = [None] * N
        for i, v in enumerate(value):
            self.value[i] = v
        self.comp = lambda x, y: True if y is None else False if x is None else comp(x,y)^reverse
        for i in range(N-2,-1,-1):
            left_i, right_i = self.node[2*i+1], self.node[2*i+2]
            left_v, right_v = self.value[left_i], self.value[right_i]
            self.node[i] = left_i if self.comp(left_v, right_v) else right_i

    def update(self, n, v):
        self.value[n] = v
        i = (self.N-1) + n
        while i > 0:
            i = (i-1)//2
            left_i, right_i = self.node[2*i+1], self.node[2*i+2]
            left_v, right_v = self.value[left_i], self.value[right_i]
            new_i = left_i if self.comp(left_v, right_v) else right_i
            if new_i == self.node[i] and new_i != n:
                break
            else:
                self.node[i] = new_i

    def at(self, n):
        if n is None:
            return None
        else:
            return self.value[n]

    def query(self, l=0, r=-1):
        return self.at(self.query_index(l,r))

    def query_index(self, l=0, r=-1):
        if r < 0: r = self.N
        L = l + self.N; R = r + self.N
        s = None
        while L < R:
            if R & 1:
                R -= 1
                if self.comp(self.at(self.node[R-1]), self.at(s)):
                    s = self.node[R-1]
            if L & 1:
                if self.comp(self.at(self.node[L-1]), self.at(s)):
                    s = self.node[L-1]
                L += 1
            L >>= 1; R >>= 1
        return s

N, M, L = inpl()
road = [[] for _ in range(N)]
for i in range(M):
    A, B, C = inpl()
    if C <= L:
        road[A-1].append((B-1,C))
        road[B-1].append((A-1,C))
minimum = [ [-1]*N for _ in range(N)]
for i in range(N):
    minimum[i][i] = 0

INF = 10**4
Q = int(input())
ST = [inpl() for _ in range(Q)]
starts = set([ s-1 for s,t in ST])
segtree = SegmentTree(N=N)
for start in starts:
    for i in range(N):
        segtree.update(i, (INF,0))
    segtree.update(start, (0,0))
    while True:
        p = segtree.query_index()
        pnred = segtree.at(p)
        if pnred is None:
            break
        else:
            pn, pred = pnred
            if pn >= INF:
                break
        minimum[start][p] = pn
        segtree.update(p, None)

        for q, c in road[p]:
            if segtree.at(q) is None:
                continue
            else:
                qn, qred = segtree.at(q)
            if pred + c > L:
                qn2, qred2 = pn + 1, c
            else:
                qn2, qred2 = pn, pred + c
            if qn < 0 or (qn2,qred2) < (qn,qred):
                segtree.update(q, (qn2, qred2))

for s,t in ST:
    print(minimum[s-1][t-1])

Submission status: Time Limit Exceeded

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

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

distance = [[float('inf')]*N for _ in range(N)]
for i in range(N):
    distance[i][i] = 0
for _ in range(M):
    a, b, c = map(int, input().split())
    distance[a-1][b-1] = c
    distance[b-1][a-1] = c

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

stoke = [[1 if distance[i][j] <= L else float('inf') for j in range(N)] for i in range(N)]
for i in range(N):
    stoke[i][i] = 0
for k in range(N):
    for i in range(N):
        for j in range(N):
            stoke[i][j] = min(stoke[i][j], stoke[i][k]+stoke[k][j])

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def warshall_floyd(N: int, graph: list) -> list:
    """ ワーシャルフロイド(頂点数, 隣接行列(0-indexed)) """
    from copy import deepcopy

    res = deepcopy(graph)
    for i in range(N):
        # 始点 = 終点、は予め距離0にしておく
        res[i][i] = 0
    # 全頂点の最短距離
    for k in range(N):
        for i in range(N):
            for j in range(N):
                res[i][j] = min(res[i][j], res[i][k] + res[k][j])
    return res

N, M, L = MAP()
G = list2d(N, N, INF)
for i in range(M):
    a, b, c = MAP()
    a -= 1
    b -= 1
    G[a][b] = c
    G[b][a] = c

res = warshall_floyd(N, G)

G2 = list2d(N, N, INF)
for i in range(N):
    for j in range(i, N):
        # 最短距離がL以下の2点なら燃料1回で行ける
        if res[i][j] <= L:
            G2[i][j] = 1
            G2[j][i] = 1

# 燃料使用回数をコストとした最短経路
res2 = warshall_floyd(N, G2)

for i in range(INT()):
    a, b = MAP()
    a -= 1
    b -= 1
    ans = res2[a][b]
    if ans != INF:
        print(ans-1)
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
def warshall_floyd(d):
    for k in range(len(d)):
        for i in range(len(d)):
            for j in range(len(d)):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d


INF = 10**9 + 1

if __name__ == "__main__":
    N, M, L = map(int, input().split())
    D = [[INF] * N for _ in range(N)]
    for i in range(N):
        D[i][i] = 0
    for i in range(M):
        tmp = list(map(int, input().split()))
        D[tmp[0]-1][tmp[1]-1] = tmp[2]
        D[tmp[1]-1][tmp[0]-1] = tmp[2]
    Q = int(input())
    st = list()
    for i in range(Q):
        st.append(list(map(int, input().split())))

    D = warshall_floyd(D)

    for i in range(N):
        for j in range(N):
            if i == j:
                D[i][j] = 0
            elif D[i][j] <= L:
                D[i][j] = 1
            else:
                D[i][j] = INF

    D = warshall_floyd(D)

    for i in range(Q):
        ans = D[st[i][0]-1][st[i][1]-1] - 1
        if ans == INF - 1:
            print(-1)
        else:
            print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 4 5 5
# 1 2 4
# 1 3 2
# 3 2 1
# 2 4 2
# 3 4 5
# 1
# 1 4

# >>> 0

################################

# from collections import deque
from heapq import *

N, M, L = map(int, input().split())
ABC = [list(map(int, input().split())) for _ in range(M)]
Q = int(input())
ST = [list(map(int, input().split())) for _ in range(Q)]

d = [[] for _ in range(N)]
for a, b, c in ABC:
    d[a-1].append((b-1, c))
    d[b-1].append((a-1, c))

# print(d)

# スタートをiにしてdijkstra * N
a_to_b = []
for i in range(N):
    # (ここまでの燃料補給回数, 使った燃料(L-残り燃料))
    i_to_b = [(10**24, 10**24) for _ in range(N)]
    i_to_b[i] = (0, 0)

    visited = [0]*N
    
    q = [(i_to_b[i], i)]
    while q:
        # print(q)
        (_, _), ti = heappop(q)
        tb, tm = i_to_b[ti]

        for ni, nm in d[ti]:
            if visited[ni]:
                continue
            if tm+nm <= L:
                n_bm = (tb, tm+nm)
            elif nm <= L:
                n_bm = (tb+1, nm)
            else:
                n_bm = (10**24, 10**24)
            # print(i, (ni, ), (tb, tm), n_bm, i_to_b[ni])
            i_to_b[ni] = min(i_to_b[ni], n_bm)
            heappush(q, (i_to_b[ni], ni))
            # print(i_to_b)
        visited[ti] = 1
    a_to_b.append(i_to_b)
    # print(i_to_b)

# print(a_to_b)

for s, t in ST:
    r = a_to_b[s-1][t-1][0]
    print(-1 if r == 10**24 else r)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n, m, l = map(int, input().split())

tm = np.full((n, n), np.inf)
for i in range(n): tm[i][i] = 0

for _ in range(m):
	a, b, c = map(int, input().split())
	a -= 1
	b -= 1
	c = float(c)
	tm[a][b] = c
	tm[b][a] = c

def wf(mat, n):
	for k in range(n):
		for i in range(n):
			for j in range(n):
				mat[i][j] = min(mat[i][j], mat[i][k]+mat[k][j])
	return mat

tm = wf(tm, n)

um = np.ones((n,n))
for i in range(n):
	for j in range(n):
		if tm[i][j] > l:
			um[i][j] = 2*n

um = wf(um,n)



q = int(input())
for _ in range(q):
	s,t = map(int, input().split())
	ans = um[s-1][t-1]
	if ans > n:
		ans = -1
	else:
		ans -= 1
	print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n, m, l = map(int, input().split())

tm = np.full((n, n), 10**9+1, dtype=np.int)
for i in range(n): tm[i][i] = 0 

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

def wf(mat, n):
	for k in range(n):
		for i in range(n):
			for j in range(n):
				mat[i][j] = min(mat[i][j], mat[i][k]+mat[k][j])
	return mat

tm = wf(tm, n)

um = np.ones((n,n), dtype=np.int)
for i in range(n):
	for j in range(n):
		if tm[i][j] > l:
			um[i][j] = 2*n

um = wf(um,n)



q = int(input())
for _ in range(q):
	s,t = map(int, input().split())
	ans = um[s-1][t-1]
	if ans > n:
		ans = -1
	else:
		ans -= 1
	print(ans)

Submission status: Time Limit Exceeded

Solution code:
inf = float('inf')
def dijkstra(s):
    d = [(inf, 1)] * N
    used = [False] * N
    d[s] = (0, -L)  
    while True:
        v = -1
        for i in range(N):
            if used[i]:
                continue
            if v==-1:
                v = i
            else:
                v = min(v, i, key = lambda x:d[x])
        if v == -1:
            break
        used[v] = True   
        m, r = d[v]
        r = -r
        for nv in range(N):
            c = cost[v][nv]
            if r>=c:
                d[nv] = min(d[nv],(m, -(r-c)))
            elif c<=L:
                d[nv] = min(d[nv], (m+1, -(L-c)))
    return d
N, M, L = map(int, input().split())
cost = [[inf]*N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    cost[a-1][b-1] = c
    cost[b-1][a-1] = c
ans = []
for i in range(N):
    ans.append(dijkstra(i))
Q = int(input())
for _ in range(Q):
    a, b = map(int, input().split())
    res = ans[a-1][b-1][0]
    print(res if res<10**10 else -1)

Submission status: Time Limit Exceeded

Solution code:
def wf(d):
    N = len(d)
    for i in range(N):
        for j in range(N):
            for k in range(N):
                d[j][k] = min(d[j][k], d[j][i] + d[i][k])
    return d


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

D = [[10 ** 20 for i in range(N+1)] for j in range(N+1)]

for i in range(N+1):
    D[i][i] = 0

for i in range(M):
    a_i, b_i, c_i = list(map(int, input().split()))
    D[a_i][b_i] = c_i
    D[b_i][a_i] = c_i

D = wf(D)

for i in range(N+1):
    for j in range(N+1):
        if i == j:
            continue
        if D[i][j] <= L:
            D[i][j] = 1
        else:
            D[i][j] = 10**20

D = wf(D)

Q = int(input())

ans = []
for i in range(Q):
    s_i, t_i = list(map(int, input().split()))
    d = D[s_i][t_i]
    if d < 10**20:
        ans.append(d-1)
    else:
        ans.append(-1)

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,m,l = LI()
    aa = [LI() for _ in range(m)]
    q = I()
    qa = [LI_() for _ in range(q)]

    e = collections.defaultdict(list)
    for a,b,c in aa:
        if c > l:
            continue
        a -= 1
        b -= 1
        e[a].append((b,c))
        e[b].append((a,c))

    def search(s):
        d = collections.defaultdict(lambda: (inf, inf))
        d[s] = (0,-l)
        q = []
        heapq.heappush(q, ((0,-l), s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True
            kk = k[0]
            kl = k[1]

            for uv, ud in e[u]:
                if v[uv]:
                    continue
                if kl + ud > 0:
                    vd = (kk+1, -l+ud)
                else:
                    vd = (kk, kl+ud)
                if d[uv] > vd:
                    d[uv] = vd
                    heapq.heappush(q, (vd, uv))

        return d

    dd = {}
    for i in range(n):
        d = search(i)
        for k in range(n):
            v = d[k]
            if v[0] == inf:
                d[k] = -1
            else:
                d[k] = v[0]
        dd[i] = d

    rr = []
    for s,t in qa:
        rr.append(dd[s][t])

    return JA(rr, "\n")


print(main())

Submission status: Time Limit Exceeded

Solution code:
import heapq
inf = 10**11
def dijkstra(v0):
    d = [(inf, inf)] * N
    d[v0] = (0, L)
    edgelist = []
    for v, c in G[v0]:
        if c<=L:
            heapq.heappush(edgelist,(0, -(L-c), v))
    while len(edgelist):
        c, r, v = heapq.heappop(edgelist)
        r = -r
        if d[v][0] != inf:
            continue
        d[v] = (c, r)
        for nv, nr in G[v]:
            if d[nv][0] == inf:
                if nr<=r:
                    heapq.heappush(edgelist,(c, -(r-nr), nv))
                elif nr<L:
                    heapq.heappush(edgelist,(c+1,-(L-nr), nv))
    return d
N, M, L = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    G[a-1].append((b-1, c))
    G[b-1].append((a-1, c))
ans = []
for i in range(N):
    ans.append(dijkstra(i))
Q = int(input())
for _ in range(Q):
    a, b = map(int, input().split())
    res = ans[a-1][b-1][0]
    print(res if res<10**10 else -1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heappush, heappop
input = sys.stdin.readline
def inpl(): return list(map(int, input().split()))

N, M, L = inpl()
G = [[] for _ in range(N)]
G2 = [[999]*(N) for _ in range(N)]

for _ in range(M):
    a, b, c = inpl()
    if c <= L:
        G[a-1].append([b-1, c])
        G[b-1].append([a-1, c])

for i in range(N):
    supply = [999]*N
    remain = [0]*N
    supply[i] = 1
    remain[i] = L
    Q = [(1, -L, i)]
    while Q:
        s, r, p = heappop(Q)
        r = -r
        if s > supply[p]:
            continue
        if (s == supply[p]) and (r < remain[p]):
            continue
        for q, c in G[p]:
            if r >= c:
                if supply[q] > s:
                    supply[q] = s
                    remain[q] = r - c
                    heappush(Q, (s, c-r, q))
                elif (supply[q] == s) & (remain[q] < r - c):
                    remain[q] = r-c
                    heappush(Q, (s, c-r, q))
            else:
                if supply[q] > (s + 1):
                    supply[q] = s + 1
                    remain[q] = L - c
                    heappush(Q, (s+1, c-L, q))
                elif (supply[q] == (s+1)) & (remain[q] < L - c):
                    supply[q] = s+1
                    remain[q] = L-c
                    heappush(Q, (s+1, c-L, q))
    for j in range(N):
        G2[i][j] = supply[j]


for _ in range(int(input())):
    s, t = inpl()
    if G2[s-1][t-1] == 999:
        print(-1)
    else:
        print(G2[s-1][t-1]-1)

Submission status: Time Limit Exceeded

Solution code:
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    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


n, m, l = map(int, input().split())
d = [[10**12 for i in range(n)] for i in range(n)]
for i in range(m):
    ai, bi, ci = map(int, input().split())
    d[ai-1][bi-1] = ci
    d[bi-1][ai-1] = ci
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０

d = warshall_floyd(d)
for i in range(n):
    for j in range(n):
        if d[i][j] <= l:
            d[i][j] = 1
        else:
            d[i][j] = 10**12

d = warshall_floyd(d)

q = int(input())
for i in range(q):
    si, ti = map(int, input().split())
    if d[si-1][ti-1] >= 10**12:
        print(-1)
    else:
        print(d[si-1][ti-1]-1)

Submission status: Time Limit Exceeded

Solution code:
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    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


n, m, l = map(int, input().split())
d = [[float("inf") for i in range(n)] for i in range(n)]
for i in range(m):
    ai, bi, ci = map(int, input().split())
    d[ai-1][bi-1] = ci
    d[bi-1][ai-1] = ci
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０

d = warshall_floyd(d)
for i in range(n):
    for j in range(n):
        if d[i][j] <= l:
            d[i][j] = 1
        else:
            d[i][j] = float("inf")

d = warshall_floyd(d)

q = int(input())
for i in range(q):
    si, ti = map(int, input().split())
    if d[si-1][ti-1] == float('inf'):
        print(-1)
    else:
        print(d[si-1][ti-1]-1)

Submission status: Time Limit Exceeded

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


def input(): return sys.stdin.readline()[:-1]


sys.setrecursionlimit(10**8)
INF = 1001001001001
n, m, l = map(int, input().split())
D = [[INF]*n for i in range(n)]

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

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


for i in range(n):
    for j in range(n):
        D[i][j] = 1 if D[i][j] <= l else INF

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])
# for i in D:
#     print(i)

q = int(input())
for i in range(q):
    s, g = map(int, input().split())
    s -= 1
    g -= 1
    print(D[s][g]-1 if D[s][g] != INF else -1)

Submission status: Time Limit Exceeded

Solution code:
#################################
##ワーシャルフロイド法 n~3
#################################
def warshall_floyd(n,d):
    #d[i][j]: iからjへの最短距離
    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
##############################
#from scipy.sparse.csgraph import csgraph_from_dense,dijkstra,floyd_warshall
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = int(0)
N,M,L =LI()
s = []
t = []
dp = [[inf] * (N) for _ in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    dp[a-1][b-1] = c
    dp[b-1][a-1] = c
Q = I()
for i in range(Q):
    a,b = LI()
    s.append(a-1)
    t.append(b-1)

for i in range(N):
    dp[i][i] = 0

#print(warshall_floyd(N,dp))
d1 = [[0] * (N) for _ in range(N)]
d1 = warshall_floyd(N,dp)
#G = csgraph_from_dense(dp)
#d1 = floyd_warshall(G)

newdp = [[inf] * (N) for _ in range(N)]
for i in range(N):
    for j in range(i+1,N):
        if d1[i][j]<=L:
            newdp[i][j] = 1
            newdp[j][i] = 1

for i in range(N):
    newdp[i][i] = 0
#print(newdp)
#print(warshall_floyd(N,newdp))
d2 = [[0] * (N) for _ in range(N)]
d2 = warshall_floyd(N,newdp)
#G2 = csgraph_from_dense(newdp)
#d2 = floyd_warshall(G2)

for i in range(Q):
    ans = d2[s[i]][t[i]]-1
    if ans!= inf:
        print(int(ans))
    else:
        print("-1")

Submission status: Time Limit Exceeded

Solution code:
INF = 1001001001

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

fuel = [[INF] * N for _ in range(N)]
for i in range(M):
    A, B, C = map(int, input().split())
    A -= 1
    B -= 1
    fuel[A][B] = C
    fuel[B][A] = C
for i in range(N):
    fuel[i][i] = 0

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

dist = [[INF] * N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if i == j:
            dist[i][j] = 0
        elif fuel[i][j] <= L:
            dist[i][j] = 1

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

Q = int(input())
for i in range(Q):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
    if dist[s][t] == INF:
        print(-1)
    else:
        print(dist[s][t] - 1)

Submission status: Time Limit Exceeded

Solution code:
n,m,l=map(int,input().split())
inf=10000000000
g=[[inf for i in range(n)] for j in range(n)]
for i in range(m):
    a,b,c=map(int,input().split())
    g[a-1][b-1]=c
    g[b-1][a-1]=c
for k in range(n):
    for i in range(n):
        for j in range(n):
            g[i][j]=min(g[i][j],g[i][k]+g[k][j])
r=[[inf for i in range(n)] for j in range(n)]
for i in range(n):
    for j in range(n):
        if g[i][j]<=l:
            r[i][j]=1
        elif g[i][j]>=inf:
            r[i][j]=inf
for k in range(n):
    for i in range(n):
        for j in range(n):
            r[i][j]=min(r[i][j],r[i][k]+r[k][j])
q=int(input())
for i in range(q):
    s,e=map(int,input().split())
    if r[s-1][e-1]>=inf:
        print(-1)
    else:
        print(r[s-1][e-1]-1)

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m,l = LI()
    v = [[] for i in range(n)]
    for i in range(m):
        a,b,c = LI()
        a -= 1
        b -= 1
        v[a].append((b,c))
        v[b].append((a,c))
    ans = [[[float("inf")]*2 for j in range(n)] for i in range(n)]
    q = []
    for s in range(n):
        ans[s][s] = [0,0]
        heappush(q,(0,0,s))
        while q:
            da,dx,x = heappop(q)
            if [da,dx] > ans[s][x]:
                continue
            for y,w in v[x]:
                if w > l:
                    continue
                nd = dx+w
                if nd <= l:
                    na = da
                    nd_ = nd
                else:
                    na = da+1
                    nd_ = w
                if [na,nd_] < ans[s][y]:
                    ans[s][y] = [na,nd_]
                    heappush(q,(na,nd_,y))
    q = I()
    for _ in range(q):
        s,t = LI()
        s -= 1
        t -= 1
        ds = ans[s][t][0]
        if ds == float("inf"):
            print(-1)
        else:
            print(ds)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
INF = 10000000000
import math
def main():
    N, M, L = map(int, input().split())
    d = [[INF for i in range(N)] for j in range(N)]
    d[0][0] = 0
    ans_d = [[INF for i in range(N)] for j in range(N)]
    ans_d[0][0] = 0
    for i in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        if c > L:
            continue 
        d[a][b] = c
        d[b][a] = c
    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])

    for i in range(N):
        for j in range(N):
            if d[i][j] <= L:
                ans_d[i][j] = 1
                ans_d[j][i] = 1

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

    Q = int(input())
    for i in range(Q):
        s, t = map(int, input().split())
        s -= 1
        t -= 1
        if d[s][t] == INF:
            print(-1)
        else:
            print(ans_d[s][t] - 1)



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

path = [[float("inf") for i in range(301)] for i in range(301)]
def dijkstra(s,n,l):
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        for i in range(n):
            if (not used[i]) and (v == -1):
                v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
            break
        used[v] = True
        dist_v = d[v]
        for j, weight in enumerate(path[v]):
            if(j == n):
                break
            alt = dist_v + weight
            r = (dist_v - 1) // l
            if r != ((alt - 1) // l) and dist_v != 0:
                alt = (r + 1) * l + weight         
            d[j] = min(d[j],alt)
    return d

n,m,l = map(int, input().split())
ans_list = []
for i in range(m):
  a,b,cost = map(int, input().split())
  a -= 1
  b -= 1
  if cost <= l:
    path[a][b] = cost
    path[b][a] = cost
for s in range(n):
  ans_list.append(dijkstra(s,n,l))
q = int(input())

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