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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,M,L=MI()
    inf=10**15
    d=[[inf]*N for _ in range(N)]
    for i in range(M):
        a,b,c=MI()
        a-=1
        b-=1
        if c<=L:
            d[a][b]=c
            d[b][a]=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])
                
    d2=[[inf]*N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if 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])
                
    Q=I()
    for i in range(Q):
        s,t=MI()
        s-=1
        t-=1
        ans=d2[s][t]
        if ans>=inf:
            print(-1)
        else:
            print(ans-1)
                
    

main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

n, m, l = map(int, readline().split())
graph = [[0] * n for _ in range(n)]
inf = float('inf')
for i in range(m):
    a, b, c = map(int, readline().split())
    graph[a - 1][b - 1] = c
    graph[b - 1][a - 1] = c
cost = floyd_warshall(csr_matrix(graph))
cnt = [[0] * n for _ in range(n)]
for i, cost_i in enumerate(cost):
    for j, v in enumerate(cost_i):
        if l >= v:
            cnt[i][j] = 1
cnt = floyd_warshall(csr_matrix(cnt))
q = int(readline())
for _ in range(q):
    s, t = map(int, readline().split())
    if cnt[s - 1][t - 1] == inf:
        print(-1)
    else:
        print(int(cnt[s - 1][t - 1] - 1))

Submission status: Accepted

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

INF = 10 ** 18
lst1 = [[INF] * (N + 1) for _ in range(N+1)] #頂点1に隣接する辺以外の道の管理
# u-->vへコストlで行ける時
for i in range(N+1):
    lst1[i][i] = 0
for _ in range(M):
    a, b, c = map(int, input().split())
    lst1[a][b] = c
    lst1[b][a] = c

# 処理する部分
def WarshallFloyd(lst):
    for k in range(N+1):
        for i in range(N+1):
            for j in range(N+1):
                lst[i][j] = min(lst[i][j], lst[i][k] + lst[k][j])
    return
# i-->jのコストはlst[i][j]

WarshallFloyd(lst1)

lst2 = [[INF] * (N + 1) for _ in range(N + 1)]
for i in range(N):
    lst2[i][i] = 0
    for j in range(i + 1, N + 1):
        if lst1[i][j] <= L:
            lst2[i][j] = 1
            lst2[j][i] = 1

WarshallFloyd(lst2)

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    if lst2[s][t] >= INF:
        print (-1)
    else:
        print (max(lst2[s][t] - 1, 0))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N,M,L = map(int,input().split())
ABC = [tuple(map(int,input().split())) for i in range(M)]
Q = int(input())
ST = [tuple(map(int,input().split())) for i in range(Q)]

INF = 10**20
g = [[INF]*N for _ in range(N)]
for a,b,c in ABC:
    a,b = a-1,b-1
    g[a][b] = g[b][a] = c
for i in range(N):
    g[i][i] = 0
for k in range(N):
    for i in range(N):
        for j in range(N):
            if g[i][j] > g[i][k] + g[k][j]:
                g[i][j] = g[i][k] + g[k][j]

h = [[N]*N for _ in range(N)]
for i in range(N-1):
    for j in range(i+1,N):
        if g[i][j] <= L:
            h[i][j] = h[j][i] = 1
for i in range(N):
    h[i][i] = 0
for k in range(N):
    for i in range(N):
        for j in range(N):
            if h[i][j] > h[i][k] + h[k][j]:
                h[i][j] = h[i][k] + h[k][j]

ans = []
for s,t in ST:
    s,t = s-1,t-1
    if h[s][t] == N:
        ans.append(-1)
    else:
        ans.append(h[s][t] - 1)
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import itertools
class WarshallFloyd:
    def __init__(self,n):
        self.v = n
        self.d = [[1e100]*n for _ in range(n)]
        for i in range(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()
tank = WarshallFloyd(n)
for i,j in itertools.combinations(range(n),2):
    if d[i][j] <= l:
        tank.path(i,j,1)
d = tank.build()
q = int(input())
ans = [0]*q
for i in range(q):
    s,t = map(int,input().split())
    ans[i] = d[s-1][t-1] - 1 if d[s-1][t-1] != 1e100 else -1
print('\n'.join(str(i) for i in ans))

Submission status: Accepted

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 = [[10**12]*(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] = 10**12
d = warshall_floid(d)
q = int(readline())
for i in range(q):
    s,t = map(int,readline().split())
    if d[s][t] >= 10**12:
        print(-1)
    else:
        print(d[s][t]-1)

Submission status: Accepted

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

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

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

edge=[n*[10**18]for _ in range(n)]
for i in range(n):
  edge[i][i]=0
for i in range(m):
  a,b,c=map(int,input().split())
  a-=1
  b-=1
  edge[a][b]=edge[b][a]=c
edge=warshall_floyd(edge)

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

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

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall
N,M,L,*X = map(int, open(0).read().split())
ls = X[:3*M]
Els = [[0]*N for i in range(N)]
Q = X[3*M]
query = X[3*M+1:]
for a,b,c in zip(*[iter(ls)]*3):
  if c<=L:
    Els[a-1][b-1] = c
    Els[b-1][a-1] = c
dist = floyd_warshall(Els)
      
Els2 = [[1 if dist[i][j]<=L else 0 for j in range(N)] for i in range(N)]
ans = floyd_warshall(Els2)

for s,t in zip(*[iter(query)]*2):
  if ans[s-1][t-1]==float('inf'):
    print(-1)
    continue
  print(int(ans[s-1][t-1])-1)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall
N,M,L,*X = map(int, open(0).read().split())
ls = X[:3*M]
Els = [[0]*N for i in range(N)]
Q = X[3*M]
query = X[3*M+1:]
for a,b,c in zip(*[iter(ls)]*3):
  if c<=L:
    Els[a-1][b-1] = c
    Els[b-1][a-1] = c
dist = floyd_warshall(Els)
      
Els2 = [[0]*N for i in range(N)]
for i in range(N):
  for j in range(N):
    if dist[i][j]<=L:
      Els2[i][j] = 1
ans = floyd_warshall(Els2)

for s,t in zip(*[iter(query)]*2):
  if ans[s-1][t-1]==float('inf'):
    print(-1)
    continue
  print(int(ans[s-1][t-1])-1)

Submission status: Accepted

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 if G[a-1][b-1]<10**18 else -1)

Submission status: Accepted

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

Solution code:
n,m,l=map(int,input().split())
cost=[[10**9+1]*n for i in range(n)]
length=[[10**9]*n for i in range(n)]
for i in range(m):
    a,b,c=map(int,input().split())
    a-=1
    b-=1
    cost[a][b]=c
    cost[b][a]=c
q=int(input())
st=[map(int,input().split())for i in range(q)]

for k in range(n):
    for i in range(n):
        for j in range(n):
            cost[i][j]=min(cost[i][j],cost[i][k]+cost[k][j])
for i in range(n):
    length[i][i]=0
for i in range(n):
    for j in range(n):
        if cost[i][j]<=l:
            length[i][j]=0
for k in range(n):
    for i in range(n):
        for j in range(n):
            length[i][j]=min(length[i][j],length[i][k]+length[k][j]+1)
for s,t in st:
    ch=min(length[s-1][t-1],length[t-1][s-1])
    print(-1 if ch>10**8 else ch)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
N,M,L=map(int,input().split())

def warshall_floyd(d):
  #d[i][j]: iからjへの最短距離
  for k in range(size_v):
    for i in range(size_v):
      for j in range(size_v):
        d[i][j]=min(d[i][j],d[i][k]+d[k][j])
  return d

# vlistに点のリスト、dist[vi][vj]に辺(vi,vj)のコストを入れて呼び出す
size_v=N+1
dist=[[float("inf")]*size_v for i in range(size_v)]
for _ in range(M):
  A,B,C=map(int,input().split())
  dist[A][B]=C
  dist[B][A]=C
for i in range(size_v):
  dist[i][i]=0 #自身のところに行くコストは0

dist=warshall_floyd(dist)
#print(dist)

dist2=[[float("inf")]*size_v for i in range(size_v)]
for i in range(size_v):
  for j in range(size_v):
    if dist[i][j]<=L:
      dist2[i][j]=1
for i in range(size_v):
  dist2[i][i]=0 #自身のところに行くコストは0

dist2=warshall_floyd(dist2)
#print(dist2)

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

Submission status: Accepted

Solution code:
import sys
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

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

d=[[sys.maxsize]*(n) for _ in range(n)]
e=[[sys.maxsize]*(n) for _ in range(n)]
for i in range(n):
  d[i][i] = 0
  e[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

d=floyd_warshall(csr_matrix(d))
for i in range(n):
  for j in range(n):
    if d[i][j] <= l:
      e[i][j] = 1

e=floyd_warshall(csr_matrix(e))

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

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

N,M,L = map(int,readline().split())
ABC = [list(map(int,readline().split())) for _ in range(M)]
Q = int(readline())
ST = [list(map(int,readline().split())) for _ in range(Q)]
    
def warshall_floyd(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

INF = 10**11
d = [[INF]*N for i in range(N)] 
a =  [[INF]*N for i in range(N)] 
for x,y,z in ABC:
    if z <= L:
      d[x-1][y-1] = z
      d[y-1][x-1] = z
for i in range(N):
    d[i][i] = 0
    a[i][i] = 1
d = csr_matrix(d)
d = floyd_warshall(csgraph=d)

for i in range(N-1):
  for j in range(i+1,N):
    if d[i][j] <= L:
      a[i][j] = 1
      a[j][i] = 1
a = csr_matrix(a)
a = floyd_warshall(csgraph=a)

for s,t in ST:
  ans = a[s-1][t-1]
  if ans == INF:
      print(-1)
  else:
      print(int(ans)-1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,M,L = map(int,readline().split())
ABC = [list(map(int,readline().split())) for _ in range(M)]
Q = int(readline())
ST = [list(map(int,readline().split())) for _ in range(Q)]
    
def warshall_floyd(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

INF = 10**11
d = [[INF]*N for i in range(N)] 
a =  [[INF]*N for i in range(N)] 
for x,y,z in ABC:
    if z <= L:
      d[x-1][y-1] = z
      d[y-1][x-1] = z
for i in range(N):
    d[i][i] = 0
    a[i][i] = 1
chk = warshall_floyd(d)

for i in range(N-1):
  for j in range(i+1,N):
    if chk[i][j] <= L:
      a[i][j] = 1
      a[j][i] = 1
ans = warshall_floyd(a)

for s,t in ST:
  answer = ans[s-1][t-1]
  if answer == INF:
      print(-1)
  else:
      print(answer-1)

Submission status: Accepted

Solution code:
import sys
def main():
    input=sys.stdin.readline
    n,m,l=map(int,input().split())
    edge=[[] for i in range(n)]
    for _ in range(m):
        a,b,c=map(int,input().split())
        if c>l:
            continue
        a-=1
        b-=1
        edge[a].append((c,b))
        edge[b].append((c,a))
    def dijkstra(s):
        used=[False for _ in range(n)]
        dist=[(10**18,10**18) for _ in range(n)]
        dist[s]=(0,0)
        for _ in range(n):
            (time,cons),x=min([(dist[i],i) for i in range(n) if not used[i]])
            used[x]=True
            for cost,nx in edge[x]:
                ntime,ncons=dist[nx]
                if l-cons>=cost:
                    if ntime>time:
                        dist[nx]=(time,cons+cost)
                    elif ntime==time:
                        if ncons>cons+cost:
                            dist[nx]=(time,cons+cost)
                else:
                    if ntime>time+1:
                        dist[nx]=(time+1,cost)
                    elif ntime==time+1:
                        if ncons>cost:
                            dist[nx]=(ntime,cost)
        return dist
    ans=[]
    #print(edge)
    for s in range(n):
        ans.append(dijkstra(s))
    q=int(input())
    for _ in range(q):
        s,t=map(int,input().split())
        s-=1
        t-=1
        if ans[s][t][0]==10**18:
            print(-1)
        else:
            print(ans[s][t][0])
if __name__=="__main__":
  main()

Submission status: Accepted

Solution code:
MOD = 10 **9 + 7
INF = 10 ** 10
import numpy as np
from  scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

def main():
    n,m,l = map(int,input().split())
    dist = [[np.inf] * n for _ in range(n)]  
    for _ in range(m):
        a,b,c = map(int,input().split())
        a -= 1
        b -= 1
        dist[a][b] = c
        dist[b][a] = c

    csr = csr_matrix(dist)
    dist1 = floyd_warshall(csr,directed = False)
    dist1 = np.where(dist1 <= l,1,np.inf)
    cnt = floyd_warshall(dist1,directed = False)
    cnt[cnt == np.inf] = 0
    cnt = cnt.astype(int)
    q = int(input())
    for _ in range(q):
        s,t = map(int,input().split())
        s -= 1
        t -= 1
        print(cnt[s][t] - 1)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
MOD = 10 **9 + 7
INF = 10 ** 10
import numpy as np
from  scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

def main():
    n,m,l = map(int,input().split())
    dist = [[INF] * n for _ in range(n)]  
    for _ in range(m):
        a,b,c = map(int,input().split())
        a -= 1
        b -= 1
        dist[a][b] = c
        dist[b][a] = c

    csr = csr_matrix(dist)
    dist1 = floyd_warshall(csr)
    dist1 = np.where(dist1 <= l,1,INF)
    cnt = floyd_warshall(dist1)
    q = int(input())
    for _ in range(q):
        s,t = map(int,input().split())
        s -= 1
        t -= 1
        print(-1 if cnt[s][t] == INF  else int(cnt[s][t]) - 1)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def warshall_floyd(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])
 
N, M, L = map(int, input().split())
D1 = [[10**18]*N for _ in range(N)]
 
for i in range(N):
    D1[i][i] = 0
 
for _ in range(M):
    A, B, C = map(int, input().split())
    D1[A-1][B-1] = C
    D1[B-1][A-1] = C

warshall_floyd(D1)
D2 = [[10**18]*N for _ in range(N)]

for i in range(N):
    D2[i][i] = 0
    
for i in range(N):
    for j in range(N):
        if i!=j and D1[i][j]<=L:
            D2[i][j] = 1

warshall_floyd(D2)
Q = int(input())

for _ in range(Q):
    s, t = map(int, input().split())
    ans = D2[s-1][t-1]
    
    if ans==10**18:
        print(-1)
    else:
        print(ans-1)

Submission status: Accepted

Solution code:
#全点対間最短経路を求めるアルゴリズム

def warshall_floyd(d):
    #d[i][j]:iからjに行く最短経路
    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

import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**9)

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

INF = 10 ** 11
d = [[INF]*(n+1) for _ in range(n+1)]
for i in range(m):
        x, y, z = map(int, input().split())
        if z <= l:
            d[x][y] = z
            d[y][x] = z #無向グラフならつける

for i in range(1,n+1):
    d[i][i] = 0

    

ss = warshall_floyd(d)



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


#補給回数
vv = warshall_floyd(ss)

for i in range(1,n+1):
    for j in range(1,n+1):
        if vv[i][j] == INF:
            vv[i][j] = -1

q = int(input())
for _ in range(q):
    x, y = map(int, input().split())
    if vv[x][y] != -1:
    	print(vv[x][y]-1)
    else:
      	print(vv[x][y])

Submission status: Accepted

Solution code:
import sys
 
input = sys.stdin.buffer.readline
 
n, m, limit = map(int, input().split())
infi = 10 ** 15
graph = [[infi] * (n + 1) for _ in range(n + 1)]
step = [[infi] * (n + 1) for _ in range(n + 1)]
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a][b] = c
    graph[b][a] = c

for k in range(1, n + 1):
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            graph[i][j] = min(graph[i][k] + graph[k][j], graph[i][j])
for i in range(1, n + 1):
    for j in range(1, n + 1):
        if graph[i][j] <= limit:
            graph[i][j] = 1
        elif graph[i][j] == 0:
            graph[i][j] = 0
        else:
            graph[i][j] = infi
for k in range(1, n + 1):
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            graph[i][j] = min(graph[i][k] + graph[k][j], graph[i][j])
 
 
q = int(input())
for _ in range(q):
    a, b = map(int, input().split())
    if graph[a][b] == infi:
        graph[a][b] = 0
    print(graph[a][b] - 1 if graph[a][b] != infi else -1)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.buffer.readline

n, m, limit = map(int, input().split())
infi = 10 ** 15
graph = [[infi] * (n + 1) for _ in range(n + 1)]
step = [[infi] * (n + 1) for _ in range(n + 1)]
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a][b] = c
    graph[b][a] = c
for i in range(1, n + 1):
    graph[i][i] = 0
for k in range(1, n + 1):
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            graph[i][j] = min(graph[i][k] + graph[k][j], graph[i][j])
for i in range(1, n + 1):
    for j in range(1, n + 1):
        if graph[i][j] <= limit:
            graph[i][j] = 1
        elif graph[i][j] == 0:
            graph[i][j] = 0
        else:
            graph[i][j] = infi
for k in range(1, n + 1):
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            graph[i][j] = min(graph[i][k] + graph[k][j], graph[i][j])


q = int(input())
for _ in range(q):
    a, b = map(int, input().split())
    if graph[a][b] == infi:
        graph[a][b] = 0
    print(graph[a][b] - 1 if graph[i][j] != infi else -1)

Submission status: Accepted

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

class WarshallFloyd:
    def __init__(self,n):
        self.v = n
        self.d = [[1e100]*n for _ in range(n)]
        for i in range(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])

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)
wf.build()
d = [[1e100]*n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if i == j:
            d[i][j] = 0
        elif wf.d[i][j] <= l:
            d[i][j] = 1

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

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

Submission status: Accepted

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

Solution code:
# scipy使う場合
import sys
input = sys.stdin.readline
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

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

# m行の入力から距離を値に持つ隣接行列を作成 0-indexed
# directed:無向グラフならFalse、有向グラフならTrue
def make_d_matrix(n,m,directed=False):
    inf = 10**13
    d = [[inf] * n for _ in range(n)]
    if(directed):
        for _ in range(m):
            a,b,c = map(int, input().split())
            d[a-1][b-1] = c
    else:
        for _ in range(m):
            a,b,c = map(int, input().split())
            d[a-1][b-1] = c
            d[b-1][a-1] = c
    return d

d = make_d_matrix(n,m)
csr_graph = csr_matrix(d)
d1 = floyd_warshall(csr_graph,directed=False)

inf = 10**3
for i in range(n):
    for j in range(n):
        d1[i][j] = 1 if (d1[i][j] <= l) else inf

csr_graph = csr_matrix(d1)
d2 = floyd_warshall(csr_graph,directed=False)

q = int(input())

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

Submission status: Accepted

Solution code:
# scipy使う場合
import sys
input = sys.stdin.readline
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

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

# m行の入力から距離を値に持つ隣接行列を作成 0-indexed
# directed:無向グラフならFalse、有向グラフならTrue
def make_d_matrix(n,m,directed=False):
    inf = 10**13
    d = [[inf] * n for _ in range(n)]
    if(directed):
        for _ in range(m):
            a,b,c = map(int, input().split())
            d[a-1][b-1] = c
    else:
        for _ in range(m):
            a,b,c = map(int, input().split())
            d[a-1][b-1] = c
            d[b-1][a-1] = c
    return d

d = make_d_matrix(n,m)
csr_graph = csr_matrix(d)
d1 = floyd_warshall(csr_graph,directed=False)

inf = 10**3
for i in range(n):
    for j in range(n):
        d1[i][j] = 1 if (d1[i][j] <= l) else inf

csr_graph = csr_matrix(d1)
d2 = floyd_warshall(csr_graph,directed=False)

q = int(input())

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

Submission status: Accepted

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

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

# ワーシャルフロイド
def warshall_floyd(d,n):
    #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

# m行の入力から距離を値に持つ隣接行列を作成 0-indexed
# directed:無向グラフならFalse、有向グラフならTrue
def make_d_matrix(n,m,directed=False):
    inf = 10**13
    d = [[inf] * n for _ in range(n)]
    if(directed):
        for _ in range(m):
            a,b,c = map(int, input().split())
            d[a-1][b-1] = c
    else:
        for _ in range(m):
            a,b,c = map(int, input().split())
            d[a-1][b-1] = c
            d[b-1][a-1] = c
    return d

d = make_d_matrix(n,m)
d = warshall_floyd(d,n)

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

d = warshall_floyd(d,n)

q = int(input())

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

Submission status: Accepted

Solution code:
n, m, l = [int(i) for i in input().split()]
d = [[10 ** 18] * n for _ in range(n)]
for i in range(n):
    d[i][i] = 0

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

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

d2 = [[10 ** 18] * n for _ in range(n)]
for i in range(n):
    d2[i][i] = 0

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

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

q = int(input())
for _ in range(q):
    s, t = [int(i) - 1 for i in input().split()]
    if d2[s][t] == 10 ** 18:
        print(-1)
    else:
        print(d2[s][t]-1)