https://atcoder.jp/contests/abc143/submissions/12257779
- ワーシャルフロイド法を使ってショートカットを追加
- 補給回数の新しいグラフを作る
任意の頂点で燃料を満タンにリセットするため、単純な最短距離が最善とはならない。ワーシャルフロイド法を使うことで、Lリットルで行ける頂点s→tが分かる。そのような頂点を結ぶショートカットを新たに追加し、給油回数の新しいグラフG'を作る。辺コストは全て1で良い。もう一度グラフG'にワーシャルフロイド法を適用(制約上ワーシャルフロイド法以外はTLEする可能性が高い)して答えを得る。計算量は