7K12 blog

猫でも分かるアルゴリズム解説

ABC143 E - Travel by Car

f:id:tkr987:20200526015511p:plain

 https://atcoder.jp/contests/abc143/submissions/12257779

  • ワーシャルフロイド法を使ってショートカットを追加
  • 補給回数の新しいグラフを作る

f:id:tkr987:20200526020506p:plain

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