ABC143 E - Travel by Car

問題原文

E - Travel by Car

問題要旨

町と道が重み付き無向連結グラフの形で与えられ、この町の間を容量Lリットルの燃料タンクを持つ車で移動することを考える。移動距離１につき、燃料を１消費し、燃料が０になればそれ以上は進めない。また、各町で燃料を最大まで補給できる。この条件のもと、 個の以下のクエリに答えよ。 - 町 [tax:s] から 町 まで移動するのに必要な、最小の燃料の補給回数を求めよ。たどり着けない場合には を出力せよ。

考えたこと

• ワーフロは使いそう

考えるべきこと

• まず与えられたグラフでワーフロ
• 次に手に入れた全点間最短経路をもとに、 「距離 以下で移動できる頂点間にコスト１の辺を張ったグラフ」をつくる
• このグラフに対してワーフロをすればいい
• 各辺の重みが何を意味しているのか？を意識する必要がある
• 何となくで解こうとしないこと

実装

import sys
from scipy.sparse.csgraph import floyd_warshall
N, M, L = map(int, input().split())
INF = 10 ** 9 + 1
G = [[float('inf')] * N for i in range(N)]
for i in range(M):
    a, b, c = map(int, sys.stdin.readline().split())
    a, b = a - 1, b - 1
    G[a][b] = c
    G[b][a] = c


# 全点間最短距離を計算
G = floyd_warshall(G)


# コストL以下で移動可能な頂点間にコスト１の辺を張る
E = [[float('inf')] * N for i in range(N)]
for i in range(N):
    for j in range(N):
        if G[i][j] <= L:
            E[i][j] = 1


# そのグラフの全点間最短距離を求める
E = floyd_warshall(E)


# クエリに答えていく
Q = int(input())
for i in range(Q):
    s, t = map(int, sys.stdin.readline().split())
    s, t = s - 1, t - 1
    print(int(E[s][t] - 1) if E[s][t] != float('inf') else - 1)

scipyしゅき