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 numpy as np
from scipy.sparse.csgraph import shortest_path
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse.csgraph import csgraph_from_dense

INF = float('inf')

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

    # G[x][y]: xからyへ直接移動するときのコスト。移動できない場合はINF
    G = [[INF] * (N+1) for n in range(N+1)]

    for i in range(M):
        a, b, c = map(int, input().split())
        G[a][b] = c
        G[b][a] = c
    G = csgraph_from_dense(G, null_value=INF)

    Q = int(input())
    Queries = []
    for i in range(Q):
        s, t = map(int, input().split())
        Queries.append((s, t))

    # ワーシャルフロイド法で、全点間の距離を求める
    cost = floyd_warshall(G)
    # 全点間の距離のうち、移動距離がL以内でおさまる頂点同士は、給油せずにすむ
    # そこで、全点間の距離のうち、移動距離がL以内でおさまる頂点同士を距離1で結んだグラフを作成し、
    # そのグラフに対してワーシャルフロイド法で最短距離を計算することで、
    # refuel[x][y] =「xからyへ移動するときの給油回数+1」というグラフを作成できる
    no_refuel = [[1 if x <= L else INF for x in c] for c in cost]
    no_refuel = csgraph_from_dense(no_refuel, null_value=INF)
    refuel_count = floyd_warshall(no_refuel)

    ans = []
    for s, t in Queries:
        d = refuel_count[s][t]
        ans.append(int(d-1) if d != INF else -1)
    
    print(*ans, sep='\n')

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:
import sys
readline = sys.stdin.readline

import math

# 最短距離をワーシャルフロイドで求める
# 最短距離がL以下の街には燃料1で行けるので、辺を貼り直してワーシャルフロイド

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

import numpy as np
from scipy.sparse.csgraph import shortest_path
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse.csgraph import csgraph_from_dense
INF = 10 ** 9 + 1
G = [[INF for i in range(N)] for j in range(N)]
for i in range(M):
  a,b,c = map(int,readline().split())
  G[a - 1][b - 1] = c
  G[b - 1][a - 1] = c
G = csgraph_from_dense(G, null_value=INF)
d = floyd_warshall(G)

EG = [[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:
      EG[i][j] = 1

EG = csgraph_from_dense(EG, null_value=INF)
d = floyd_warshall(EG)

Q = int(readline())
for i in range(Q):
  s,t = map(int,readline().split())
  if d[s - 1][t - 1] != math.inf:
    print(int(d[s - 1][t - 1] - 1))
  else:
    print(-1)

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:
#!/usr/bin/env python3

N, M, L = [int(s) for s in input().split()]
edge = [[int(s) for s in input().split()] for _ in range(M)]
dist = [[10 ** 10] * N for _ in range(N)]
graph = [[] for _ in range(N)]
Q = int(input())

for i, j, w in edge:
    dist[i - 1][j - 1] = w
    dist[j - 1][i - 1] = w

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

for i in range(N):
    for j in range(N):
        dist[i][j] = 1 if dist[i][j] <= L else 10 ** 10

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


for _ in range(Q):
    s, t = [int(a) - 1 for a in input().split()]
    print(dist[s][t] - 1 if dist[s][t] < 10**10 else -1)

Submission status: Accepted

Solution code:
import sys
from heapq import heappop, heappush
from scipy.sparse.csgraph import floyd_warshall
input = sys.stdin.readline
 
def main():
    n,w,l = map(int,input().split())
    d = [[10**15 for _ in range(n)] for _ in range(n)]
    for _ in range(w):
        x,y,z = map(int,input().split())
        x -= 1
        y -= 1
        if z > l:
            continue
        d[x][y] = z
        d[y][x] = z
    for i in range(n):
        d[i][i] = 0
    d = floyd_warshall(d)
    G = [[10**15 for _ in range(n)] for _ in range(n)]
    for i in range(n-1):
        for j in range(i+1,n):
            if d[i][j] <= l:
                G[i][j] = 1
                G[j][i] = 1
    for i in range(n):
        G[i][i] = 0
    G = floyd_warshall(G)
    q = int(input())
    for _ in range(q):
        s,t = map(int,input().split())
        s -= 1
        t -= 1
        ans = G[s][t]
        if ans == 10**15:
            print(-1)
            continue
        print(int(ans)-1)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

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

N, M, L = map(int, input().split())
INF = 10**18
G = [[INF]*N for i in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    if c <= L:
        G[a][b] = c
        G[b][a] = 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])
G2 = [[INF]*N for i in range(N)]
for i in range(N):
    for j in range(N):
        if G[i][j] <= L:
            G2[i][j] = 1
for k in range(N):
    for i in range(N):
        for j in range(N):
            G2[i][j] = min(G2[i][j], G2[i][k]+G2[k][j])
Q = int(input())
ans = []
for i in range(Q):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
    if G2[s][t] == INF:
        ans.append(-1)
    else:
        ans.append(G2[s][t]-1)
print(*ans, sep="\n")

Submission status: Accepted

Solution code:
N, M, L = map(int, input().split())
INF = 10**18
G = [[INF]*N for i in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    if c <= L:
        G[a][b] = c
        G[b][a] = 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])
G2 = [[INF]*N for i in range(N)]
for i in range(N):
    for j in range(N):
        if G[i][j] <= L:
            G2[i][j] = 1
for k in range(N):
    for i in range(N):
        for j in range(N):
            G2[i][j] = min(G2[i][j], G2[i][k]+G2[k][j])
Q = int(input())
ans = []
for i in range(Q):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
    if G2[s][t] == INF:
        ans.append(-1)
    else:
        ans.append(G2[s][t]-1)
print(*ans, sep="\n")

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
E - Travel by Car
https://atcoder.jp/contests/abc143/tasks/abc143_e

"""
import sys


from scipy.sparse.csgraph import floyd_warshall

def main(args):
    N, M, L = map(int, input().split())
    g1 = [[float('inf')] * (N+1) for _ in range(N+1)]
    for i in range(N+1):
        g1[i][i] = 0
    for _ in range(M):
        A, B, C = map(int, input().split())
        g1[A][B] = g1[B][A] = C
    d1 = floyd_warshall(g1)
    g2 = [[float('inf')] * (N+1) for _ in range(N+1)]
    for i in range(N+1):
        for j in range(N+1):
            if i == j:
                g2[i][j] = 0
            elif d1[i][j] <= L:
                g2[i][j] = g2[j][i] = 1
    d2 = floyd_warshall(g2)
    Q = int(input())
    for _ in range(Q):
        s, t = map(int, input().split())
        print(-1 if d2[s][t] == float('inf') else int(d2[s][t]) - 1)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
from queue import deque
readline = sys.stdin.buffer.readline
#sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def main():
    N, M, L = geta(int)
    INF = 10**10

    d = [[INF] * (N + 1) for _ in range(N + 1)]

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

    for _ in range(M):
        a, b, c = geta(int)
        d[a][b] = c
        d[b][a] = c

    def warshall_froyd(_d):
        for k in range(1, N + 1):
            for i in range(1, N + 1):
                for j in range(1, N + 1):
                    l = _d[i][k] + _d[k][j]
                    if _d[i][j] > l:
                        _d[i][j] = l

    warshall_froyd(d)

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

    warshall_froyd(f)

    for _ in range(gete(int)):
        s, t = geta(int)
        ret = f[s][t]
        print(ret - 1 if ret != INF else -1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, m, l = map(int, input().split())
def warshall_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])

inf = 10 ** 15
d = [[inf] * n for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    d[a-1][b-1] = min(d[a-1][b-1], c)
    d[b-1][a-1] = min(d[b-1][a-1], c)

warshall_floyd(d, n)

e = [[inf] * n for _ in range(n)]
for i in range(n):
    for j in range(i+1, n):
        if d[i][j] <= l:
            e[i][j] = min(e[i][j], 1)
            e[j][i] = min(e[j][i], 1)

warshall_floyd(e, n)


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

Submission status: Accepted

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

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

import sys
input = sys.stdin.readline

INF = float("INF")

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

cost = [[INF] * N for _ in range(N)]
for i in range(N):
    cost[i][i] = 0

for _ in range(M):
    v1, v2, w = map(int, input().split())
    v1, v2 = v1-1, v2-1
    cost[v1][v2] = w
    cost[v2][v1] = w

for k in range(N):
    for i in range(N):
        for j in range(N):
            if cost[i][j] > cost[i][k] + cost[k][j]:
                cost[i][j] = cost[i][k] + cost[k][j]

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

for k in range(N):
    for i in range(N):
        for j in range(N):
            if cost[i][j] > cost[i][k] + cost[k][j]:
                cost[i][j] = cost[i][k] + cost[k][j]

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
 
n, m, l = map(int, input().split())
 
INF = float("INF")
 
d = [[INF] * n for _ 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
 
for k in range(n):
    for i in range(n):
        for j in range(n):
            if d[i][j] > d[i][k] + d[k][j]:
                d[i][j] = d[i][k] + d[k][j]
 
# print()
# print(*d, sep='\n')
 
for i in range(n):
    for j in range(n):
        if i == j:
            continue
 
        if d[i][j] <= l:
            d[i][j] = 1
        else:
            d[i][j] = INF
 
for k in range(n):
    for i in range(n):
        for j in range(n):
            if d[i][j] > d[i][k] + d[k][j]:
                d[i][j] = d[i][k] + d[k][j]
 
# print()
# print(*d, sep='\n')
 
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(d[s][t]-1)

Submission status: Accepted

Solution code:
def resolve():
    from scipy.sparse.csgraph import floyd_warshall
    import sys
    def input(): return sys.stdin.readline().rstrip()
    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
    x = floyd_warshall(ar, directed=False)
    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
    y = floyd_warshall(br, directed=False)
    q = int(input())
    for _ in range(q):
        s, t = map(int, input().split())
        print(int(y[s - 1, t - 1]) - 1 if y[s - 1, t - 1] < inf else -1)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
def resolve():
    from scipy.sparse.csgraph import floyd_warshall
    import sys
    def input(): return sys.stdin.readline().rstrip()
    n, m, l = map(int, input().split())
    inf = float("inf")
    ar = [[0] * n for _ in range(n)]
    for _ in range(m):
        a, b, c = map(int, input().split())
        ar[a - 1][b - 1] = c
    x = floyd_warshall(ar, directed=False)
    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
    y = floyd_warshall(br, directed=False)
    q = int(input())
    for _ in range(q):
        s, t = map(int, input().split())
        print(int(y[s - 1, t - 1]) - 1 if y[s - 1, t - 1] < inf else -1)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
def resolve():
    from scipy.sparse.csgraph import floyd_warshall
    import sys
    def input(): return sys.stdin.readline().rstrip()
    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
    x = floyd_warshall(ar, directed=False)
    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
    y = floyd_warshall(br, directed=False)
    q = int(input())
    for _ in range(q):
        s, t = map(int, input().split())
        p = y[s - 1, t - 1]
        print(int(y[s - 1, t - 1]) - 1 if y[s - 1, t - 1] < inf else -1)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

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
    x = floyd_warshall(ar, directed=False)
    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
    y = floyd_warshall(br, 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: Accepted

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

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 = np.zeros((n, 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 = np.zeros((n, 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: Accepted

Solution code:
import numpy as np
from scipy.sparse.csgraph import dijkstra
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 = dijkstra(csr_matrix(graph), directed=False)
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 = dijkstra(csr_matrix(graph), directed=False)
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: Accepted

Solution code:
from heapq import *
INF = 1e10

def floyd(n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]

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

floyd(N)

grafo2 = [[INF] * N for i in range(N)]

for x in range(N):
    for y in range(N) :
        if d[x][y] <= L:
            grafo2[x][y] = 1

for k in range(N):
    for i in range(N):
        for j in range(N):
            if grafo2[i][j] > grafo2[i][k] + grafo2[k][j]:
                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: Accepted

Solution code:
import numpy as np
from scipy.sparse.csgraph import dijkstra
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 = dijkstra(csr_matrix(graph), directed=False)
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 = dijkstra(csr_matrix(graph), directed=False)
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: Accepted

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="FW")
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="FW")
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: Accepted

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="D")
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="D")
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: Accepted

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product

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

Solution code:
import sys

def main():
  input = sys.stdin.readline
  n, m, l = map(int, input().split())
  
  inf = pow(10, 10)
  towns = [[inf]*n for _ in range(n)]
  
  for _ in range(m):
    a, b, c = map(int, input().split())
    if c > l:
      continue
    towns[a-1][b-1] = c
    towns[b-1][a-1] = c
  
  for k in range(n):
    for i in range(n):
      for j in range(n):
        if towns[i][j] > towns[i][k]+towns[k][j] and l >= towns[i][k]+towns[k][j]:
          towns[i][j] = towns[i][k]+towns[k][j]
  
  for i in range(n):
    for j in range(n):
      if towns[i][j] == inf:
        continue
      towns[i][j] = 0
  
  for k in range(n):
    for i in range(n):
      for j in range(n):
        if towns[i][j] > towns[i][k]+towns[k][j]+1:
          towns[i][j] = towns[i][k]+towns[k][j]+1

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

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

sys.setrecursionlimit(10 ** 7)

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

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


n, m, l = na()
abc = nan(m)
q = ni()
st = nan(q)

g = [[] for _ in range(n)]
dist = [[inf] * n for _ in range(n)]
for i in range(m):
    a, b, c = abc[i]
    a -= 1
    b -= 1
    dist[a][b] = c
    dist[b][a] = c

floyd_warshall(n, dist)

ans = [[inf] * n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if dist[i][j] <= l:
            ans[i][j] = 1
            ans[j][i] = 1

floyd_warshall(n, ans)

for i in range(q):
    s, t = st[i]
    s -= 1
    t -= 1
    if ans[s][t] >= inf:
        print(-1)
    else:
        print(ans[s][t] - 1)

Submission status: Accepted

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


def dijkstra(start, matrix):
    # O(V^2)ダイクストラ
    INF = 10 ** 18
    n = len(matrix)
    used = [False] * n
    # 補給回数: 少ないほうがいい
    # 使用燃料: 少ないほうがいい
    # 補給回数が少ないほうがより嬉しい
    # dist[v] = 補給回数 * (10 ** 15) + 使用燃料
    dist = [INF] * n
    dist[start] = 0
    while True:
        v = -1
        for u in range(n):
            if not used[u] and (v == -1 or dist[u] < dist[v]):
                v = u
        if v == -1:
            break
        used[v] = True
        for nxt_v in range(n):
            tmp = merge(dist[v], matrix[v][nxt_v])
            dist[nxt_v] = min(dist[nxt_v], tmp)
    return dist

def merge(d, cost):
    div_d, mod_d = divmod(d + cost, 10 ** 15)
    if mod_d > l:
        new_d = (div_d + 1) * 10 ** 15 + cost
    else:
        new_d = d + cost
    return new_d


n, m, l = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
q = int(input())
query = [list(map(int, input().split())) for i in range(q)]
INF = 10 ** 18

# 隣接行列
matrix = [[INF] * n for i in range(n)]
for i in range(n):
    matrix[i][i] = 0
for a, b, cost in info:
    a -= 1
    b -= 1
    if cost > l:
        continue
    matrix[a][b] = cost
    matrix[b][a] = cost

ans = [[0] * n for i in range(n)] 
for i in range(n):
    tmp = dijkstra(i, matrix)
    for j in range(n):
        ans[i][j] = tmp[j] // (10 ** 15)

for a, b in query:
    a -= 1
    b -= 1
    if ans[a][b] == 1000:
        print(-1)
    else:
        print(ans[a][b])

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    inf = 10**17
    #mod = 10**9 + 7

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

    #kを経由してiからjに行く行き方を考える
    #これで上手く行くのは与えられた辺の和しか考えていないため
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if dp[i][j] > dp[i][k] + dp[k][j]:
                    dp[i][j] = dp[j][i] = dp[i][k]+dp[k][j]

    dp2 =  [[inf]*N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if dp[i][j] <= L:
                dp2[i][j] = dp2[j][i] = 1

    for k in range(N):
        for i in range(N):
            for j in range(N):
                if dp2[i][j] > dp2[i][k] + dp2[k][j]:
                    dp2[i][j] = dp2[j][i] = dp2[i][k]+dp2[k][j]

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
INF = 10 ** 14
N, M, L = map(int,input().split())

MAP1 = [[INF for i in range(N)] for j in range(N)]

for _ in range(M):
    A, B, C = map(int,input().split())
    MAP1[A-1][B-1] = C
    MAP1[B-1][A-1] = C

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

MAP2 = [[INF for i in range(N)] for j in range(N)]

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

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

Q = int(input())

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