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: Runtime Error

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
    #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in range(base**n):s=[tb//(base**bt)%base for bt in range(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
read=sys.stdin.buffer.read
readline=sys.stdin.buffer.readline
input=lambda: sys.stdin.readline().rstrip()

class Tree:
    def __init__(self,inp_size=None,ls=None,init=True,index=1):
        self.LCA_init_stat=False
        self.ETtable=[]
        if init:
            if ls==None:
                self.stdin(inp_size,index=index)
            else:
                self.size=len(ls)+1
                self.edges,_=GI(self.size,self.size-1,ls,index=index)
        return
 
    def stdin(self,inp_size=None,index=1):
        if inp_size==None:
            self.size=int(input())
        else:
            self.size=inp_size
        self.edges,_=GI(self.size,self.size-1,index=index)
        return
    
    def listin(self,ls,index=0):
        self.size=len(ls)+1
        self.edges,_=GI(self.size,self.size-1,ls,index=index)
        return
 
    def dfs(self,x,func=lambda pr,prv,nx,dist:prv+dist,root_v=0):
        q=deque([x])
        v=[None]*self.size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=func(c,v[c],nb,d)
        return v
 
    def bfs(self,x,func=lambda pr,prv,nx,dist:prv+dist,root_v=0):
        q=deque([x])
        v=[None]*self.size
        v[x]=root_v
        while q:
            c=q.popleft()
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=func(c,v[c],nb,d)
        return v
 
    def parent(self,x):
        return self.dfs(0,func=lambda pr,prv,nx,dist:pr,root_v=-1)
 
    def topological_sort(self,x):  # return topological sort of the tree
        tps=[]
        q=deque([x])
        v=[None]*self.size
        v[x]=0
        while q:
            c=q.popleft()
            tps.append(c)
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=0
        return tps
 
    def EulerTour(self,x):
        q=deque()
        q.append(x)
        self.depth=[None]*self.size
        self.depth[x]=0
        self.ETtable=[]
        self.ETdepth=[]
        self.ETin=[-1]*self.size
        self.ETout=[-1]*self.size
        cnt=0
        while q:
            c=q.pop()
            if c<0:
                ce=~c
            else:
                ce=c
                for nb,d in self.edges[ce]:
                    if self.depth[nb]==None:
                        q.append(~ce)
                        q.append(nb)
                        self.depth[nb]=self.depth[ce]+1
            self.ETtable.append(ce)
            self.ETdepth.append(self.depth[ce])
            if self.ETin[ce]==-1:
                self.ETin[ce]=cnt
            else:
                self.ETout[ce]=cnt
            cnt+=1
        return
    
    def LCA_init(self,root):
        self.EulerTour(root)
        self.st=SparseTable(self.ETdepth,init_func=min,init_idl=inf)
        #self.st=SegTree(self.size*2-1,self.ETdepth,function=min,ide=inf)
        self.LCA_init_stat=True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            self.LCA_init(root)
        xin,xout=self.ETin[x],self.ETout[x]
        yin,yout=self.ETin[y],self.ETout[y]
        a=min(xin,yin)
        b=max(xout,yout,xin,yin)
        id_of_min_dep_in_et=self.st.query_id(a,b+1)
        return self.ETtable[id_of_min_dep_in_et]
 
    def __str__(self):
        return  str(self.edges)
 
    def show(self):
        if all([all([d==1 for nd,d in edge]) for edge in self.edges]):
            print( [[nd for nd,d in edge] for edge in self.edges] )
        else:
            print(self)
 
class SparseTable: # O(N log N) for init, O(1) for query(l,r)
    def __init__(self,ls,init_func=min,init_idl=float('inf')):
        self.func=init_func
        self.idl=init_idl
        self.size=len(ls)
        self.N0=self.size.bit_length()
        self.table=[ls[:]]
        self.index=[list(range(self.size))]
        self.lg=[0]*(self.size+1)
        
        for i in range(2,self.size+1):
            self.lg[i]=self.lg[i>>1]+1
 
        for i in range(self.N0):
            tmp=[self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) for j in range(self.size)]
            tmp_id=[self.index[i][j] if self.table[i][j]==self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) else self.index[i][min(j+(1<<i),self.size-1)] for j in range(self.size)]
            self.table+=[tmp]
            self.index+=[tmp_id]
    
    # return func of [l,r)
    def query(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        return self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))])
    
    # return index of which val[i] = func of v among [l,r)
    def query_id(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        a,b=self.index[N][l],self.index[N][max(0,r-(1<<N))]
        if self.table[0][a]==self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))]):
            b=a
        return b
    
    # return boundary index of r such that func({table[i]} =< x , i in [pos,r]
    def right_bound(self,pos,x):
        k=(self.size-pos).bit_length()
        for j in range(k)[::-1]:
            nx=pos+(1<<j)
            if nx<n and self.query(pos,nx+1)<=x:
                pos+=(1<<j)
        return pos
    
    # return boundary index of l such that func({table[i]} =< x , i in [l,pos]
    def left_bound(self,pos,x):
        k=pos.bit_length()
        for j in range(k)[::-1]:
            nx=pos-(1<<j)
            if 0<=nx and self.query(nx,pos+1)<=x:
                pos-=(1<<j)
        return pos
 
    def __str__(self):
        return str(self.table[0])
 
    def print(self):
        for i in self.table:
            print(*i)

def dijkstra(st):
    # edge=[[(v_to,dist_to_v),...],[],...]
    # initialize: def: d=dist(st,i), prev=[previous vertex in minimum path], q[]
    #n=len(edge)
    d=[(0 if st==i else inf) for i in range(n)]

    q=[(0,st)]
    heapify(q)
    v=[False]*n
    # calc
    while q:
        dist,cur=heappop(q)
        if v[cur]:
            continue
        v[cur]=True
        for dst,dist in edge[cur]:
            alt=d[cur]+dist
            if alt<d[dst]:
                d[dst]=alt
                heappush(q,(alt,dst))
    return d


show_flg=False
show_flg=True
ans=0

n,m,l=LI()
edge,_=GI(n,m)

d_gas=[]
g=[[]for i in rep(n)]
for i in rep(n):
    d,_=dijkstra(i)
    for j in rep(i+1,n):
        if d[j]<=l:
            g[i]+=(j,1),
            g[j]+=(i,1),


dist=[]
edge=g
for i in rep(n):
    d,_=dijkstra(i)
    dist+=[d]

#show(dist)
q=I()
for i in rep(q):
    s,t=LI_()
    ans=dist[s][t]-1
    if ans==inf-1:
        ans=-1
    print(ans)

Submission status: Runtime Error

Solution code:
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

Submission status: Runtime Error

Solution code:
from sys import stdin

if __name__ == '__main__':
    n, m, l = map(int, stdin.readline().rstrip().split())

    import heapq
    g = dict()
    for _ in range(m):
        a, b, c = map(int, stdin.readline().rstrip().split())
        if c <= l:
            if a - 1 not in g:
                g[a-1] = [(b-1, c)]
            else:
                g[a-1].append((b-1, c))
            if b - 1 not in g:
                g[b-1] = [(a-1, c)]
            else:
                g[b-1].append((a-1, c))

    ans = []
    for _ in range(n):
        ans.append([0] * n)

    for start in range(n):
        mins1 = [10 ** 9 + 1] * n # a
        mins2 = [0] * n # n

        mins1[start], mins2[start] = 0, l

        q = [(0, l, start)] # added, left_gas, pos
        heapq.heapify(q)

        while q:
            a, b, u = heapq.heappop(q)

            if (a > mins1[u]) or (a == mins1[u] and b < mins2[u]):
                continue

            for v, weight in g[u]:
                if weight > b:
                    a_new = a + 1
                    b_new = l - weight
                else:
                    a_new = a
                    b_new = b - weight

                if a_new < mins1[v] or (a_new == mins1[v] and b_new > mins2[v]):
                    mins1[v], mins2[v] = a_new, b_new
                    heapq.heappush(q, (a_new, b_new, v))

        ans[start] = mins1

    qq = int(stdin.readline().rstrip())
    for _ in range(qq):
        s, t = map(int, stdin.readline().rstrip().split())
        tmp = ans[s-1][t-1]
        if tmp == 10 ** 9 + 1:
            print(-1)
        else:
            print(tmp)

Submission status: Runtime Error

Solution code:
from sys import stdin

if __name__ == '__main__':
    n, m, l = map(int, stdin.readline().rstrip().split())
    abc = [list(map(int, stdin.readline().rstrip().split())) for _ in range(m)]
    q = int(stdin.readline().rstrip())
    st = [list(map(int, stdin.readline().rstrip().split())) for _ in range(q)]

    from collections import defaultdict
    import heapq
    g = defaultdict(list)
    for a, b, c in abc:
        if c <= l:
            g[a-1].append((b-1, c))
            g[b-1].append((a-1, c))

    starts = [s - 1 for (s, t) in st]

    ans = []
    for start in starts:
        mins = [[float('inf'), 0] for _ in range(n)] # (a, b)
        mins[start] = [0, l]

        q = [(0, l, start)] # added, left_gas, pos
        heapq.heapify(q)

        while q:
            a, b, u = heapq.heappop(q)

            if (a > mins[u][0]) or (a == mins[u][0] and b < mins[u][1]):
                continue

            for v, weight in g[u]:
                if weight > b:
                    a_new = a + 1
                    b_new = l - weight
                else:
                    a_new = a
                    b_new = b - weight

                if a_new < mins[v][0] or (a_new == mins[v][0] and b_new > mins[v][1]):
                    mins[v][0], mins[v][1] = a_new, b_new
                    heapq.heappush(q, (a_new, b_new, v))

        ans.append([_mins[0] for _mins in mins])

    for s, t in st:
        tmp = ans[s-1][t-1]
        if tmp == float('inf'):
            print(-1)
        else:
            print(tmp)

Submission status: Runtime Error

Solution code:
def resolve():
    from scipy.sparse.csgraph import floyd_warshall
    import numpy as np
    import sys
    input = sys.stdin.readline
    n, m, l = map(int, input().split())
    inf = 10 ** 20
    ar = [[inf] * n for _ in range(n)]
    for _ in range(m):
        a, b, c = map(int, input().split())
        ar[a - 1][b - 1] = c
        ar[b - 1][a - 1] = c
    x = floyd_warshall(ar)
    br = [[inf] * n for _ in range(n)]
    for i in range(n):
        for j in range(i + 1, n):
            if x[i, j] <= l:
                br[i][j] = 1
                br[j][i] = 1
    y = floyd_warshall(br)
    q = int(input())
    for _ in range(q):
        s, t = map(int, input().split())
        p = y[s - 1, t - 1]
        print(int(p) - 1 if p < inf else -1)


if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
def resolve():
    from scipy.sparse.csgraph import floyd_warshall
    import numpy as np
    import sys
    input = sys.stdin.readline
    n, m, l = map(int, input().split())
    inf = 10 ** 20
    ar = [[0] * n for _ in range(n)]
    for _ in range(m):
        a, b, c = map(int, input().split())
        ar[a - 1, b - 1] = c
        ar[b - 1, a - 1] = c
    x = floyd_warshall(ar)
    br = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(i + 1, n):
            if x[i, j] <= l:
                br[i, j] = 1
                br[j, i] = 1
    y = floyd_warshall(br)
    q = int(input())
    for _ in range(q):
        s, t = map(int, input().split())
        p = y[s - 1, t - 1]
        print(int(p) - 1 if p < inf else -1)


if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
def resolve():
    from scipy.sparse.csgraph import shortest_path
    from scipy.sparse import csr_matrix, lil_matrix
    import numpy as np
    inf = 10**20
    n, m, l = map(int, input().split())
    if m == 0:
        q = int(input())
        for _ in range(q):
            print(-1)
        return
    edge = np.array([input().split() for _ in range(m)], dtype=np.int64).T
    a = csr_matrix((edge[2], (edge[:2] - 1)), shape=(n, n))
    x = shortest_path(a, directed=False)
    b = lil_matrix((n, n), dtype=np.int64)
    for i in range(n):
        for j in range(i + 1, n):
            if x[i, j] <= l:
                b[i, j] = 1
    b = b.tocsr()
    y = shortest_path(b, directed=False)
    q = int(input())
    for _ in range(q):
        s, t = map(int, input().split())
        p = y[s - 1, t - 1]
        print(int(p) - 1 if p < inf else -1)


if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
    from heapq import *
    INF = 1e10
    respostas = []
     
    def floyd(n):
        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])
     
    N,M,L = map(int,input().split())
     
    d = [[INF]*N for i in range(N)]
     
    for x in range(M):
        a,b,w = map(int,input().split())
        d[a-1][b-1] = w
        d[b-1][a-1] = w
        d[a-1][a-1] = 0
        d[b-1][b-1] = 0
     
     
    floyd(N)
    grafo2 = [[INF] * N for i in range(N)]
     
    for x in range(len(d)):
        for y in range(len(d[x])) :
            if d[x][y] <= L:
                grafo2[x][y] = 1
                grafo2[y][x] = 1
     
     
     
    for k in range(N):
        for i in range(N):
            for j in range(N):
                grafo2[i][j] = min(grafo2[i][j], grafo2[i][k] + grafo2[k][j])
     
    query = int(input())
     
    for x in range(query):
        s,t = map(int,input().split())
        if grafo2[s-1][t-1] == INF:
            print(-1)
        else:
			print(grafo2[s-1][t-1] - 1)

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path
from scipy.sparse import csr_matrix
inf = float("inf")
N, M, L = map(int, input().split())
graph = np.zeros((N, N))
for _ in range(M):
    A, B, C = map(int, input().split())
    graph[A-1][B-1] = C
    graph[B-1][A-1] = C
shortest_paths = shortest_path(csr_matrix(graph), directed=False, method="WF")
graph = np.full((N, N), inf)
for i in range(N):
    for j in range(N):
        if shortest_paths[i][j] <= L:
            graph[i][j] = 1

Q = int(input())
def int_(num_str):
    return int(num_str) - 1

costs = shortest_path(csr_matrix(graph), directed=False, method="WF")
for _ in range(Q):
    s, t = map(int_, input().split())
    print(int(costs[s][t])-1 if costs[s][t] != inf else -1)

Submission status: Runtime Error

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n,m,l=map(int,input().split())
abc=[list(map(int,input().split())) for i in range(m)]
q=int(input())
st=[list(map(int,input().split())) for i in range(q)]

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,w = n,m #n:頂点数　w:辺の数

d = [[float("inf") for i in range(n)] for i in range(n)] 
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(w):
    x,y,z = abc[i]
    x,y=x-1,y-1
    d[x][y] = z
    d[y][x] = z
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０
tmp=warshall_floyd(d)

newd = [[float("inf") for i in range(n)] for i in range(n)]

for i in range(n):
    for j in range(i+1,n):
        if d[i][j]<=l:
            newd[i][j]=1
            newd[j][i]=1
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０

tmp=warshall_floyd(newd)

for i in range(q):
    s,t=st[i]
    s,t=s-1,t-1

    print(newd[s][t]-1 if newd[s][t]!=float('inf') else -1)

Submission status: Runtime Error

Solution code:
def warshall_floid(d):
    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())
d = [10**13]*(n+1) for i in range(n+1)]
for i in range(m):
    a,b,c = map(int,input().split())
    d[a][b] = c
    d[b][a] = c
for i in range(1,n+1):
    d[i][i] = 0
d = warshall_floid(d)
for i in range(1,n+1):
    for j in range(1,n+1):
        if d[i][j] <= l:
            d[i][j] = 1
        else:
            d[i][j] = 10**13
d = warshall_floid(d)
q = int(input())
for i in range(q):
    s,t = map(int,input().split())
    if d[s][t] >= 10**13:
        print(-1)
    else:
        print(d[s][t]-1)

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def warshall_floid(d):
    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,readline().split())
d = [[5*10**11]*(n+1) for i in range(n+1)]
for i in range(m):
    a,b,c = map(int,readline().split())
    d[a][b] = c
    d[b][a] = c
for i in range(1,n+1):
    d[i][i] = 0
d = warshall_floid(d)
for i in range(1,n+1):
    for j in range(1,n+1):
        if d[i][j] <= l:
            d[i][j] = 1
        else:
            d[i][j] = 5*10**11
d = warshall_floid(d)
q = int(input())
for i in range(q):
    s,t = map(int,readline().split())
    if d[s][t] >3*10**11:
        print(-1)
    else:
        print(d[s][t]-1)

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse import lil_matrix, csr_matrix
from scipy.sparse.csgraph import shortest_path

n,m,limit=map(int,input().split())
G=np.zeros((n,n),dtype=np.int64)
for i in range(m):
    a,b,cost=map(int,input().split())
    G[a-1,b-1]=cost
    G[b-1,a-1]=cost
G=shortest_path(G,method='FW')
for c in range(n):
    for l in range(n):
        if G[c][l]<=limit:
            G[c][l]=1
        else:
            G[c][l]=0
G=shortest_path(G,method='FW')
q=int(input())
Q=[map(int,input().split())for i in range(q)]
for a,b in Q:
    print(int(G[a-1][b-1])-1)

Submission status: Runtime Error

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

#基本的にワーシャルフロイドの場合、行列式のリストで距離を保管する
from scipy.sparse import csr_matrix
from scipy.sparse import csgraph 

d = [[10**12 for i in range(n+1)] for i in range(n+1)]

for i in range(m):
    x,y,z = map(int,input().split())
    #有向グラフか無向グラフかによってここで場合わけが生じる
    d[x][y] = z
    d[y][x] = z
    
for i in range(n+1):
    d[i][i] = 0 #自身のところに行くコストは０
q=int(input())
que=[]
for _ in range(q):
    s,t=map(int,input().split())
    que.append((s,t))
       
csr=csr_matrix(d)
K=csgraph.shortest_path(csr,method="FW",directed=True)
e = [[10**12 for i in range(n+1)] for i in range(n+1)]

for i in range(1,n+1):
    for j in range(1,n+1):
        if K[i][j]<=l:
            e[i][j]=1
            
for i in range(n+1):
    e[i][i]=0
    

A=csr_matrix(e)
ANS=csgraph.shortest_path(A,method="FW",directed=True)

for some in que:
    s,t=some[0],some[1]
    if int(ANS[s][t])<10**12:
        print(int(ANS[s][t])-1)
    else:
        print(-1)

Submission status: Runtime Error

Solution code:
import bisect

N = int(input())
A = list(map(int,input().split()))
A.sort()

SUM = 0
for i,a in enumerate(A):
    for j,b in enumerate(A[i+1:]):
        SUM += bisect.bisect_left(A[i+j+2:], a+b)

print(SUM)

Submission status: Runtime Error

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

class WarshallFloyd:
    def __init__(self,n):
        self.v = n
        self.d = []
        for i in range(n):
            self.d.append([1e100]*n)
            self.d[i][i] = 0

    def path(self,x,y,c):
        if x == y:
            return False
        self.d[x][y] = c
        self.d[y][x] = c
        return True

    def build(self):
        for k in range(self.v):
            for i in range(self.v):
                for j in range(self.v):
                    self.d[i][j] = min(self.d[i][j], self.d[i][k] + self.d[k][j])
        return self.d

n,m,l = map(int,input().split())
wf = WarshallFloyd(n)
for i in range(m):
    a,b,c = map(int,input().split())
    wf.path(a-1,b-1,c)
d = wf.build()

wf = WarshallFloyd(n)
for i in range(1,n):
    for j in range(i):
        if d[i][j] <= l:
            wf.path(i,j,1)

ans = wf.build()

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

Submission status: Runtime Error

Solution code:
from heapq import *
import sys
"""
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import time

import math
"""
"""def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
sys.setrecursionlimit(10**7)"""
input=lambda :sys.stdin.readline().rstrip()



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

data=[{} for i in range(N+1)]
se=[set() for i in range(N+1)]
data[0]=[0]
for A,B,C in ABC:
    data[A][B]=C
    data[B][A]=C
    se[A].add(B)
    se[B].add(A)
maxp=[max([l[a] for a in l]) for l in data]

d=[[[301,0]]*(N+1) for i in range(N+1)]
for i in range(1,N+1):
    visited=set()
    stack=[[0,0,i]]
    while stack:
        m,l,a=heappop(stack)
        if not a in visited:
            visited.add(a)
            if len(visited)==N:
                break
            for p in se[a]-visited:
                    c=data[a][p]
                    if c<=L:
                        if l+c>L:
                            if d[i][p]>[m+1,c]:
                                d[i][p]=[m+1,c]
                                if p>i:
                                    d[p][i]=[m+1,L]
                                heappush(stack,[m+1,c,p])
                        else:
                            if d[i][p]>=[m,l+c]:
                                d[i][p]=[m,l+c]
                                if p>i:
                                    d[p][i]=[m,l+max(maxp[p],c)]
                                heappush(stack,[m,l+c,p])
for s,t in ST:
    if d[s][t][0]!=301:
        print(d[s][t][0])
    else:
        print(-1)

Submission status: Runtime Error

Solution code:
from collections import *
from heapq import *
from itertools import *
#from fractions import gcd

from decimal import *
import copy
from bisect import *
import time
import sys
import math

input=lambda :sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**7)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))

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

data=[[] for i in range(N+1)]
for A,B,C in ABC:
    data[A].append([B,C])
    data[B].append([A,C])

d=[[301 for n in range(N+1)] for i in range(N+1)]
for i in range(1,N+1):
    visited=set()
    stack=[[0,L,i]]
    while stack:
        m,l,a=heappop(stack)
        if not a in visited:
            visited.add(a)
            d[i][a]=m
            if len(visited)==N:
                break
            for p,c in data[a]:
                if not p in visited:
                    if c<=L:
                        if l-c<0:
                            if d[i][p]>[m+1,L-c]:

                                heappush(stack,[m+1,L-c,p])
                        else:
                            if d[i][p]>[m,l-c]:
                                heappush(stack,[m,l-c,p])
for s,t in ST:
    if d[s][t]!=301:
        print(d[s][t])
    else:
        print(-1)