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: Accepted

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: Accepted

Solution code:
def main():
  import sys
  from numpy import int32
  from scipy.sparse import csr_matrix
  from scipy.sparse.csgraph import floyd_warshall
  f=floyd_warshall
  t=int32(sys.stdin.buffer.read().split())
  n,m,l=t[:3]
  t=t[3:]
  m*=3
  print('\n'.join((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]].clip(0,n)%n-1).astype(int).astype(str)))
main()

Submission status: Accepted

Solution code:
def main():
  import sys
  from numpy import int32
  from scipy.sparse import csr_matrix
  from scipy.sparse.csgraph import floyd_warshall
  f=floyd_warshall
  t=int32(sys.stdin.buffer.read().split())
  n,m,l=t[:3]
  t=t[3:]
  m*=3
  print('\n'.join(map(str,map(int,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]].clip(0,n)%n-1))))
main()

Submission status: Accepted

Solution code:
def main():
  import sys
  from numpy import int32
  from scipy.sparse import csr_matrix
  from scipy.sparse.csgraph import floyd_warshall
  t=int32(sys.stdin.buffer.read().split())
  n,m,l=t[:3]
  t=t[3:]
  m*=3
  print('\n'.join(map(str,map(int,floyd_warshall(floyd_warshall(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]].clip(0,n)%n-1))))
main()

Submission status: Accepted

Solution code:
import sys
from numpy import*
from scipy.sparse import*
def main():
  f=csgraph.floyd_warshall
  t=int32(sys.stdin.buffer.read().split())
  n,m,l=t[:3]
  t=t[3:]
  m*=3
  print('\n'.join(map(str,map(int,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]].clip(0,n)%n-1))))
main()

Submission status: Accepted

Solution code:
from numpy import*
from scipy.sparse import*
def main():
  f=csgraph.floyd_warshall
  t=int32(open(0).read().split())
  n,m,l=t[:3]
  t=t[3:]
  m*=3
  print('\n'.join(map(str,map(int,clip(f(f(csr_matrix((t[2:m:3],(t[:m:3],t[1:m:3])),(n+1,n+1)),0)<=l)[t[m+1::2],t[m+2::2]],0,n)%n-1))))
main()

Submission status: Accepted

Solution code:
from numpy import*
from scipy.sparse import*
def main():
  f=csgraph.floyd_warshall
  t=int32(open(0).read().split())
  n,m,l=t[:3]
  t=t[3:]
  m*=3
  print('\n'.join(map(str,map(int,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]].clip(0,n)%n-1))))
main()

Submission status: Accepted

Solution code:
from scipy.sparse import*
def main():
  f=csgraph.floyd_warshall
  n,m,l,*t=map(int,open(0).read().split())
  m*=3
  print('\n'.join(map(str,map(int,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]].clip(0,n)%n-1))))
main()

Submission status: Accepted

Solution code:
from scipy.sparse import*
def main():
  f=csgraph.floyd_warshall
  n,m,l,*t=map(int,open(0).read().split())
  m*=3
  *_,=map(print,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]].clip(0,n)%n-1)
main()

Submission status: Accepted

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

for i in range(N):
    for j in range(N):
        if i == j:
            distance[i][j] = 0
        elif distance[i][j] <= L:
            distance[i][j] = 1
        else:
            distance[i][j] = float('inf')

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

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

Submission status: Accepted

Solution code:
N,M,L = map(int, input().split())
A = [0]*M
B = [0]*M
C = [0]*M
for i in range(M):
    A[i], B[i], C[i] = map(int, input().split())
    
Q = int(input())
qlist = [[int(q) for q in input().split()] for _ in range(Q)]

INF = 10**18
d = [[INF]*N for _ in range(N)]
for i in range(M):
    d[A[i]-1][B[i]-1] = C[i]
    d[B[i]-1][A[i]-1] = C[i]

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

# Warshall-Floyd法
# DP
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])

d2 = [[INF]*N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if i == j:
            d2[i][j] = 0
        elif d[i][j] <= L:
            d2[i][j] = 1
            
for k in range(N):
    for i in range(N):
        for j in range(N):
            d2[i][j] = min(d2[i][j], d2[i][k]+d2[k][j])
                
for i in range(Q):
    s = qlist[i][0]-1
    t = qlist[i][1]-1
    ans = d2[s][t]
    if ans >= INF:
        print(-1)
    else:
        print(ans-1)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    n,m,l = map(int,input().split())
    d = [[10**12]*n for _ in [0]*n]
    for i in range(m):
        a,b,c = map(int,input().split())
        if l >= c:
            d[a-1][b-1] = d[b-1][a-1] = c
    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])

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

    for k in range(n):
        for i in range(n):
            for j in range(n):
                edge[i][j] = min(edge[i][j],edge[i][k] + edge[k][j])

    q = int(input())
    for _ in [0]*q:
        s,t = map(int,input().split())
        if edge[s-1][t-1] >= 10**12:
            print(-1)
        else:
            print(edge[s-1][t-1]-1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from scipy.sparse import*
f=csgraph.johnson
n,m,l,*t=map(int,open(0).read().split())
m*=3
*_,=map(print,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]].clip(0,n)%n-1)

Submission status: Accepted

Solution code:
from scipy.sparse import*
f=csgraph.johnson
n,m,l,*t=map(int,open(0).read().split())
m*=3
print(*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]].clip(0,n)%n-1,sep='\n')

Submission status: Accepted

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

n, m, l = map(int, input().split())
INF = float("inf")

def warshall_floyd(d, 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])
    return d

d = [[INF for i in range(n)] for j in range(n)]
for i in range(n): d[i][i] = 0
for i in range(m):
    a, b, c = map(int, input().split())
    a -= 1; b -= 1
    d[a][b] = c
    d[b][a] = c
d = warshall_floyd(d, n)

d2 = [[INF for i in range(n)] for j in range(n)]
for i in range(n):
    for j in range(n):
        if d[i][j] <= l: d2[i][j] = 1
    d2[i][i] = 0
d2 = warshall_floyd(d2, n)

q = int(input())
for _ in range(q):
    s, t = map(int, input().split())
    res = d2[s-1][t-1]
    print(-1 if res == INF else res-1)

Submission status: Accepted

Solution code:
S = raw_input()
S = S.split()
n,m,l = int(S[0]),int(S[1]),int(S[2])
MAX = int(1e15)
G = []
for i in xrange(n):
    temp=[]
    for j in xrange(n):
        temp.append(MAX)
    G.append(temp)
for i in xrange(n):
    G[i][i]=0

for i in xrange(m):
    S = raw_input()
    S = S.split()
    a,b,c = int(S[0]),int(S[1]),int(S[2])
    a-=1
    b-=1
    G[a][b]=c
    G[b][a]=c
for k in xrange(n):
    for i in xrange(n):
        for j in xrange(n):
            val = G[i][k]+G[k][j]
            G[i][j] = min(G[i][j],val)
dd = G
for i in xrange(n):
    for j in xrange(n):
        if(dd[i][j]<=l):
            G[i][j]=1
        else :
            G[i][j]=MAX
        if(i==j):
            G[i][j]=0

for k in xrange(n):
    for i in xrange(n):
        for j in xrange(n):
            val = G[i][k]+G[k][j]
            G[i][j] = min(G[i][j],val)
#print(G)
q = input()
while(q):
    q-=1
    S = raw_input()
    S =S.split()
    s,t = int(S[0]),int(S[1])
    s-=1
    t-=1
    p = G[s][t]
    if(p>=MAX):
        print -1
    else:
        print p-1

Submission status: Accepted

Solution code:
from scipy.sparse import*;f=csgraph.johnson;n,m,l,*t=map(int,open(0).read().split());m*=3;d=f(f(csr_matrix((t[2:m:3],(t[:m:3],t[1:m:3])),[n+1]*2),0)<=l);d[d>n]=0;print(*d[t[m+1::2],t[m+2::2]]-1,sep='\n')

Submission status: Accepted

Solution code:
from scipy.sparse import*;f=csgraph.dijkstra;n,m,l,*t=map(int,open(0).read().split());d=f(f(csr_matrix((t[2:m*3:3],(t[:m*3:3],t[1:m*3:3])),(n+1,n+1)),0)<=l);d[d>n]=0;print(*d[t[m*3+1::2],t[m*3+2::2]]-1,sep='\n')

Submission status: Accepted

Solution code:
import sys
from numpy import*
from scipy.sparse import*
f=csgraph.floyd_warshall
n,m,l,*t=map(int,sys.stdin.buffer.read().split())
t=int32(t)
d=f(f(csr_matrix((t[2:m*3:3],(t[:m*3:3],t[1:m*3:3])),(n+1,n+1)),0)<=l)-1
d[d==inf]=-1
print('\n'.join(map(str,map(int,d[t[m*3+1::2],t[m*3+2::2]]))))

Submission status: Accepted

Solution code:
import sys
from numpy import*
from scipy.sparse import*
def main():
  f=csgraph.floyd_warshall
  n,m,l,*t=map(int,sys.stdin.buffer.read().split())
  t=int32(t)
  d=f(f(csr_matrix((t[2:m*3:3],(t[:m*3:3],t[1:m*3:3])),(n+1,n+1)),0)<=l)-1
  d[d==inf]=-1
  print('\n'.join(map(str,map(int,d[t[m*3+1::2],t[m*3+2::2]]))))
main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
#import math
#import time
#import random  # randome is not available at Codeforces
def I():
    return int(input())
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 StoI():
    return [ord(i)-97 for i in input()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
#eps=10**(-10)
#ts=time.time()
#sys.setrecursionlimit(10**6)
input=lambda: sys.stdin.readline().rstrip()

show_flg=False
show_flg=True

def wf(d):
    n=len(d)
    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=MI()
d=[[inf]*n for _ in range(n)]
for i in range(m):
    a,b,c=LI_()
    d[a][b]=c+1
    d[b][a]=c+1

d=wf(d)
g=[[inf]*n for i in range(n)]

for i in range(n):
    for j in range(i+1,n):
        if d[i][j]<=l:
            g[i][j]=1
            g[j][i]=1
g=wf(g)

q=I()
for _ in range(q):
    s,t=LI_()
    if g[s][t]==inf:
        ans=-1
    else:
        ans=g[s][t]-1
    print(ans)

Submission status: Accepted

Solution code:
def main():
  import sys
  from scipy.sparse.csgraph import floyd_warshall
  n,m,l,*t=map(int,sys.stdin.buffer.read().split())
  d=[[0]*(n+1)for _ in range(n+1)]
  for a,b,c in zip(*[iter(t[:m*3])]*3):d[a][b]=c
  d=floyd_warshall(floyd_warshall(d,0)<=l)-1
  d[d>n]=-1
  print('\n'.join([str(int(d[i]))for i in zip(*[iter(t[m*3+1:])]*2)]))
main()

Submission status: Accepted

Solution code:
def main():
  import sys
  from scipy.sparse.csgraph import floyd_warshall
  n,m,l,*t=map(int,sys.stdin.buffer.read().split())
  d=[[0]*(n+1)for _ in range(n+1)]
  for a,b,c in zip(*[iter(t[:m*3])]*3):d[a][b]=c
  d=floyd_warshall(floyd_warshall(d,0)<=l)-1
  d[d>n]=-1
  print('\n'.join(map(str,[int(d[i])for i in zip(*[iter(t[m*3+1:])]*2)])))
main()

Submission status: Accepted

Solution code:
def main():
  import sys
  from scipy.sparse.csgraph import floyd_warshall
  n,m,l,*t=map(int,sys.stdin.buffer.read().split())
  d=[[0]*(n+1)for _ in range(n+1)]
  for a,b,c in zip(*[iter(t[:m*3])]*3):d[a][b]=c
  d=floyd_warshall(floyd_warshall(d,0)<=l)-1
  d[d>n]=-1
  print('\n'.join(map(str,map(int,[d[i]for i in zip(*[iter(t[m*3+1:])]*2)]))))
main()

Submission status: Accepted

Solution code:
def main():
  import sys
  from scipy.sparse.csgraph import floyd_warshall as f
  n,m,l,*t=map(int,sys.stdin.buffer.read().split())
  d=[[0]*(n+1)for _ in range(n+1)]
  for a,b,c in zip(*[iter(t[:m*3])]*3):d[a][b]=c
  d=f(f(d,0)<=l)-1
  d[d>n]=-1
  print('\n'.join(map(str,map(int,[d[i]for i in zip(*[iter(t[m*3+1:])]*2)]))))
main()

Submission status: Accepted

Solution code:
def main():
  import sys
  from scipy.sparse.csgraph import floyd_warshall as f
  n,m,l,*t=map(int,sys.stdin.buffer.read().split())
  d=[[0]*(n+1)for _ in range(n+1)]
  for a,b,c in zip(*[iter(t[:m*3])]*3):d[a][b]=c
  d=f(f(d,0)<=l)-1
  d[d>n]=-1
  print('\n'.join(map(str,[int(d[i])for i in zip(*[iter(t[m*3+1:])]*2)])))
main()

Submission status: Accepted

Solution code:
def main():
  import sys
  from scipy.sparse.csgraph import floyd_warshall as f
  n,m,l,*t=map(int,sys.stdin.buffer.read().split())
  d=[[0]*(n+1)for _ in range(n+1)]
  for a,b,c in zip(*[iter(t[:m*3])]*3):d[a][b]=c
  d=f(f(d,0)<=l)
  d[d>n]=0
  d-=1
  print('\n'.join(map(str,map(int,[d[i]for i in zip(*[iter(t[m*3+1:])]*2)]))))
main()

Submission status: Accepted

Solution code:
def main():
  import sys
  from scipy.sparse.csgraph import floyd_warshall as f
  n,m,l,*t=map(int,sys.stdin.buffer.read().split())
  d=[[0]*(n+1)for _ in range(n+1)]
  for a,b,c in zip(*[iter(t[:m*3])]*3):d[a][b]=c
  d=f(f(d,0)<=l)-1
  d[d==float('inf')]=-1
  print('\n'.join(map(str,map(int,[d[i]for i in zip(*[iter(t[m*3+1:])]*2)]))))
main()

Submission status: Accepted

Solution code:
def main():
  import sys
  from scipy.sparse.csgraph import floyd_warshall as f
  n,m,l,*t=map(int,sys.stdin.buffer.read().split())
  d=[[0]*(n+1)for _ in range(n+1)]
  for a,b,c in zip(*[iter(t[:m*3])]*3):d[a][b]=c
  d=f(f(d,0)<=l)-1
  d[d>n]=-1
  d=d.astype(int)
  print('\n'.join(map(str,[d[i]for i in zip(*[iter(t[m*3+1:])]*2)])))
main()

Submission status: Accepted

Solution code:
def main():
  import sys
  from scipy.sparse.csgraph import floyd_warshall as f
  n,m,l,*t=map(int,sys.stdin.buffer.read().split())
  d=[[0]*(n+1)for _ in range(n+1)]
  for a,b,c in zip(*[iter(t[:m*3])]*3):d[a][b]=c
  d=f(f(d,0)<=l)-1
  d[d>n]=-1
  print('\n'.join(map(str,map(int,map(d.__getitem__,zip(*[iter(t[m*3+1:])]*2))))))
main()

Submission status: Accepted

Solution code:
import sys
from scipy.sparse.csgraph import floyd_warshall as f
def main():
  n,m,l,*t=map(int,sys.stdin.buffer.read().split())
  d=[[0]*(n+1)for _ in range(n+1)]
  for a,b,c in zip(*[iter(t[:m*3])]*3):d[a][b]=c
  d=f(f(d,0)<=l)-1
  d[d>n]=-1
  d=d.astype('i2')
  print('\n'.join(map(str,map(d.__getitem__,zip(*[iter(t[m*3+1:])]*2)))))
main()

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall

N, M, L, *I = map(int, open(0).read().split())
ABC, ST = I[:3 * M], I[3 * M + 1:]

E = [[0] * N for _ in range(N)]
for a, b, c in zip(*[iter(ABC)] * 3):
    E[a - 1][b - 1] = E[b - 1][a - 1] = c

E = floyd_warshall(E)
E = [[(eij <= L) for j, eij in enumerate(ei)] for i, ei in enumerate(E)]
E = floyd_warshall(E)

INF = float("inf")

A = []
for s, t in zip(*[iter(ST)] * 2):
    a = E[s - 1][t - 1] - 1
    A.append("-1" if a == INF else str(int(a)))

print("\n".join(A))

Submission status: Accepted

Solution code:
import sys
from scipy.sparse.csgraph import floyd_warshall as f
def main():
  n,m,l,*t=map(int,sys.stdin.buffer.read().split())
  d=[[0]*(n+1)for _ in range(n+1)]
  for a,b,c in zip(*[iter(t[:m*3])]*3):d[a][b]=c
  d=f(f(d,0)<=l)-1
  d[d>n]=-1
  print('\n'.join(map(str,map(int,map(d.__getitem__,zip(*[iter(t[m*3+1:])]*2))))))
main()

Submission status: Accepted

Solution code:
import sys
from scipy.sparse.csgraph import floyd_warshall as f
input=sys.stdin.buffer.readline
def main():
  n,m,l=map(int,input().split())
  d=[[0]*(n+1)for _ in range(n+1)]
  for _ in range(m):
    a,b,c=map(int,input().split())
    d[a][b]=c
  d=f(f(d,0)<=l)-1
  d[d>n]=-1
  a=[d[tuple(map(int,input().split()))]for _ in range(int(input()))]
  print('\n'.join(map(str,map(int,a))))
main()

Submission status: Accepted

Solution code:
import sys
import scipy.sparse.csgraph as s
f=s.floyd_warshall
def main():
  n,m,l,*t=map(int,sys.stdin.buffer.read().split())
  d=[[0]*(n+1)for _ in range(n+1)]
  for a,b,c in zip(*[iter(t[:m*3])]*3):d[a][b]=c
  d=f(f(d,0)<=l)-1
  d[d>n]=-1
  print('\n'.join(map(str,map(int,[d[i]for i in zip(*[iter(t[m*3+1:])]*2)]))))
main()

Submission status: Accepted

Solution code:
import sys
from scipy.sparse.csgraph import floyd_warshall as f
def main():
  n,m,l,*t=map(int,sys.stdin.buffer.read().split())
  d=[[0]*(n+1)for _ in range(n+1)]
  for a,b,c in zip(*[iter(t[:m*3])]*3):d[a][b]=c
  d=f(f(d,0)<=l)-1
  d[d>n]=-1
  d=d.astype('i2')
  print('\n'.join(map(str,[d[i]for i in zip(*[iter(t[m*3+1:])]*2)])))
main()

Submission status: Accepted

Solution code:
import sys
from scipy.sparse.csgraph import floyd_warshall as f
def main():
  n,m,l,*t=map(int,sys.stdin.buffer.read().split())
  d=[[0]*(n+1)for _ in range(n+1)]
  for a,b,c in zip(*[iter(t[:m*3])]*3):d[a][b]=c
  d=f(f(d,0)<=l)-1
  d[d>n]=-1
  d=d.astype('i2').astype('U')
  print('\n'.join(d[i]for i in zip(*[iter(t[m*3+1:])]*2)))
main()

Submission status: Accepted

Solution code:
import sys
from scipy.sparse.csgraph import floyd_warshall as f
def main():
  n,m,l,*t=map(int,sys.stdin.buffer.read().split())
  d=[[0]*(n+1)for _ in range(n+1)]
  for a,b,c in zip(*[iter(t[:m*3])]*3):d[a][b]=c
  d=f(f(d,0)<=l)-1
  d[d>n]=-1
  print('\n'.join(str(int(d[i]))for i in zip(*[iter(t[m*3+1:])]*2)))
main()

Submission status: Accepted

Solution code:
import sys
from scipy.sparse.csgraph import floyd_warshall as f
def main():
  n,m,l,*t=map(int,sys.stdin.buffer.read().split())
  d=[[0]*(n+1)for _ in range(n+1)]
  for a,b,c in zip(*[iter(t[:m*3])]*3):d[a][b]=c
  d=f(f(d,0)<=l)
  d[d>n]=0
  print('\n'.join(map(str,map(int,[d[i]-1for i in zip(*[iter(t[m*3+1:])]*2)]))))
main()

Submission status: Accepted

Solution code:
import sys
from scipy.sparse.csgraph import floyd_warshall as f
def main():
  n,m,l,*t=map(int,sys.stdin.buffer.read().split())
  d=[[0]*(n+1)for _ in range(n+1)]
  for a,b,c in zip(*[iter(t[:m*3])]*3):d[a][b]=c
  d=f(f(d,0)<=l)-1
  d[d>n]=-1
  print('\n'.join(map(str,map(int,[d[i]for i in zip(*[iter(t[m*3+1:])]*2)]))))
main()

Submission status: Accepted

Solution code:
inf = float('inf')
def dijkstra(s):
    d = [(inf, 1)] * N
    used = [False] * N
    d[s] = (0, -L)  
    for i in range(N):
        v = -1
        for i in range(N):
            if used[i]:
                continue
            if v==-1:
                v = i
            elif d[v]>d[i]:
                v = i
        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 != inf else -1)

Submission status: Accepted

Solution code:
inf = 10**10
def dijkstra(s):
    d = [(inf, 1)] * N
    used = [False] * N
    d[s] = (0, -L)  
    for i in range(N):
        v = -1
        for i in range(N):
            if used[i]:
                continue
            if v==-1:
                v = i
            elif d[v]>d[i]:
                v = i
        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 != inf else -1)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall as f
def main():
  n,m,l,*t=map(int,open(0).read().split())
  d=[[0]*(n+1)for _ in'_'*(n+1)]
  for a,b,c in zip(*[iter(t[:m*3])]*3):d[a][b]=c
  d=f(f(d,0)<=l)-1
  d[d>n]=-1
  print('\n'.join(map(str,map(int,[d[i]for i in zip(*[iter(t[m*3+1:])]*2)]))))
main()

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall as f
def main():
  n,m,l,*t=map(int,open(0).read().split())
  d=[[0]*(n+1)for _ in range(n+1)]
  for a,b,c in zip(*[iter(t[:m*3])]*3):d[a][b]=c
  d=f(f(d,0)<=l)-1
  d[d>n]=-1
  print('\n'.join(map(str,map(int,[d[i]for i in zip(*[iter(t[m*3+1:])]*2)]))))
main()

Submission status: Accepted

Solution code:
from scipy.sparse import*
f=csgraph.floyd_warshall
def main():
  n,m,l,*t=map(int,open(0).read().split())
  d=[[0]*(n+1)for _ in range(n+1)]
  for a,b,c in zip(*[iter(t[:m*3])]*3):d[a][b]=c
  d=f(f(d,0)<=l)-1
  d[d>n]=-1
  d=d.astype('i').astype('U')
  print('\n'.join(d[i]for i in zip(*[iter(t[m*3+1:])]*2)))
main()

Submission status: Accepted

Solution code:
from scipy.sparse import*
f=csgraph.floyd_warshall
def main():
  n,m,l,*t=map(int,open(0).read().split())
  d=[[0]*(n+1)for _ in range(n+1)]
  for a,b,c in zip(*[iter(t[:m*3])]*3):d[a][b]=c
  d=f(f(d,0)<=l)-1
  d[d>n]=-1
  d=d.astype('U')
  print('\n'.join(d[i]for i in zip(*[iter(t[m*3+1:])]*2)))
main()

Submission status: Accepted

Solution code:
from scipy.sparse import*
f=csgraph.floyd_warshall
def main():
  n,m,l,*t=map(int,open(0).read().split())
  d=[[0]*(n+1)for _ in range(n+1)]
  for a,b,c in zip(*[iter(t[:m*3])]*3):d[a][b]=c
  d=f(f(d,0)<=l)-1
  d[d>n]=-1
  d=d.astype('i')
  print('\n'.join(map(str,[d[i]for i in zip(*[iter(t[m*3+1:])]*2)])))
main()

Submission status: Accepted

Solution code:
from scipy.sparse import*
f=csgraph.floyd_warshall
def main():
  n,m,l,*t=map(int,open(0).read().split())
  d=[[0]*(n+1)for _ in range(n+1)]
  for a,b,c in zip(*[iter(t[:m*3])]*3):d[a][b]=c
  d=f(f(d,0)<=l)-1
  d[d>n]=-1
  d=d.astype('i')
  print('\n'.join(str(d[i])for i in zip(*[iter(t[m*3+1:])]*2)))
main()

Submission status: Accepted

Solution code:
from scipy.sparse import*
def main():
  f=csgraph.floyd_warshall
  n,m,l,*t=map(int,open(0).read().split())
  d=[[0]*(n+1)for _ in range(n+1)]
  for a,b,c in zip(*[iter(t[:m*3])]*3):d[a][b]=c
  d=f(f(d,0)<=l)-1
  d[d>n]=-1
  print('\n'.join(map(str,map(int,[d[i]for i in zip(*[iter(t[m*3+1:])]*2)]))))
main()

Submission status: Accepted

Solution code:
from scipy.sparse import*
def main():
  f=csgraph.floyd_warshall
  n,m,l,*t=map(int,open(0).read().split())
  d=[[0]*(n+1)for _ in range(n+1)]
  for a,b,c in zip(*[iter(t[:m*3])]*3):d[a][b]=c
  d=f(f(d,0)<=l)-1
  d[d>n]=-1
  print('\n'.join(map(str,[d[i]for i in zip(*[iter(t[m*3+1:])]*2)])))
main()

Submission status: Accepted

Solution code:
from scipy.sparse import*
def main():
  f=csgraph.floyd_warshall
  n,m,l,*t=map(int,open(0).read().split())
  d=[[0]*(n+1)for _ in range(n+1)]
  for a,b,c in zip(*[iter(t[:m*3])]*3):d[a][b]=c
  d=f(f(d,0)<=l)-1
  d[d>n]=-1
  print('\n'.join(str(int(d[i]))for i in zip(*[iter(t[m*3+1:])]*2)))
main()

Submission status: Accepted

Solution code:
from scipy.sparse import*
def main():
  f=csgraph.floyd_warshall
  n,m,l,*t=map(int,open(0).read().split())
  d=[[0]*(n+1)for _ in range(n+1)]
  for a,b,c in zip(*[iter(t[:m*3])]*3):d[a][b]=c
  d=f(f(d,0)<=l)-1
  d[d>n]=-1
  print('\n'.join(str(d[i])for i in zip(*[iter(t[m*3+1:])]*2)))
main()

Submission status: Accepted

Solution code:
def e_travel_by_car(INF=float('inf')):
    from copy import deepcopy
    from scipy.sparse.csgraph import floyd_warshall
    N, M, L = [int(i) for i in input().split()]
    Roads = [[int(i) for i in input().split()] for j in range(M)]
    Q = int(input())
    Queries = [[int(i) for i in input().split()] for j in range(Q)]

    graph = [[INF] * i + [0] + [INF] * (N - i - 1) for i in range(N)]
    fuel = deepcopy(graph)

    for a, b, c in Roads:
        graph[a - 1][b - 1] = graph[b - 1][a - 1] = c
    dist = floyd_warshall(graph)

    for row in range(N):
        for col in range(row):
            fuel[row][col] = fuel[col][row] = int(dist[row][col] <= L)
    fuel = floyd_warshall(fuel)

    ans = [-1 if fuel[s - 1][t - 1] == INF else int(fuel[s - 1][t - 1]) - 1
           for s, t in Queries]
    return '\n'.join(map(str, ans))

print(e_travel_by_car())

Submission status: Accepted

Solution code:
N,M,L=map(int,input().split())
c=[[0]*N for i in range(N)]
for i in range(M):
    A,B,C=map(int,input().split())
    c[A-1][B-1]=c[B-1][A-1]=C
Q=int(input())
ST=[list(map(int,input().split())) for i in range(Q)]
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall
g=csr_matrix(c)
d=floyd_warshall(g,directed=False)
import numpy as np
c=np.array([[1 if d[i][j]<=L else 0 for j in range(N)] for i in range(N)])
g=csr_matrix(c)
d=floyd_warshall(g,directed=False)
for s,t in ST:
    x=d[s-1][t-1]
    print(int(x)-1 if x<10**9 else -1)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall

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

fuel = floyd_warshall(csgraph_from_dense(fuel))
# 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

dist = floyd_warshall(csgraph_from_dense(dist))
# 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(int(dist[s][t]) - 1)

Submission status: Accepted

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


# 頂点数 v のグラフ d の頂点 i から頂点 j への最短路を求める (O|v^3|)
def warchall_floyd(d, v):
    for k in range(v):
        for i in range(v):
            for j in range(v):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])


def main():
    N, M, L = map(int, input().split())
    inf = 10**10

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

    Q = int(input())

    F = [[inf]*N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if D[i][j] <= L:
                F[i][j] = 1
    warchall_floyd(F, N)

    ans = []
    for _ in range(Q):
        a, b = map(int, input().split())
        tmp = F[a-1][b-1]
        if tmp == inf:
            ans.append(-1)
        else:
            ans.append(tmp-1)
    for a in ans:
        print(a)


if __name__ == '__main__':
    main()