狠狠撸

C ガソリンスタンド
@takayuta1999

問題概要（言い換え）
? N 個の頂点に対して、数 ?? が与えられる
? 各頂点対 (?, ?) に対して、? → ? に長さ ?? × |? ? ?| の辺
を張る
? このとき、?個の最短路クエリに答えよ
? 1 ≦ ? ≦ 4000 , 1 ≦ ? ≦ 200,000

解法
? ワーシャルフロイド法やダイクストラ法ではサイズが大き
すぎるため、時間が間に合わない
? 性質をつかもう

解法
? 問題文にも明示されてるようにまず一列に頂点を並べて
みる
? 終点を固定して生き方を考える
1 2 3 4

解法
? 問題文にも明示されてるようにまず一列に頂点を並べて
みる
? 終点を固定して生き方を考える
（こういう誤植好き）
1 2 3 4

解法
? 終点を固定すると、ありうる道筋としては以下のどちらか
? 始点 ? と終点 ? に対して、
? からどこにも止まらずに直接 ? に行く
? から別の駅 ? に行ってその後 ? に行く

解法
? 終点を固定すると、ありうる道筋としては以下のどちらか
? 始点 ? と終点 ? に対して、
? からどこにも止まらずに直接 ? に行く
? から別の駅 ? に行ってその後 ? に行く
? 上の可能性は別に処理して下だけ考える

解法
? 最後に経由する駅 ? が ? のどちら側に存在するかで場
合分けする
? ? < ? の時を考える（ ? < ? の時も同様）

解法
? ? < ? の時を考える
? ? より左で初めて ? の値が??より大きくなるところを ? と
する（ない場合は ? = ?1）

解法
? ? < ? の時を考える
? ? より左で初めて ? の値が ??より小さくなるところを ? と
する（ない場合は ? = ?1）
? このとき、? = ? であるとしてよいことを示す

証明
? まず、? ≦ ? を示す
? もし、? < ? であるとしたら、? → ? と行かずに、途中で ?
を経由した方が明らかによい
? よって、? ≦ ?

証明
? 次に、? ≦ ? を示す
? もし、? < ? であるとしたら、? ≠ ? なので、? の一個前の
位置を場合分けすると、?? ≧ ?? だから、? に行かずにそ
のまま ? へ行ってもよいと分かり、最短経路として考えな
くてもよいと分かる
? よって、? ≦ ?

証明
? 以上より、? = ?
? 同様に、? への右からの変移も一意に定めてよい

解法
? 以上より、辺が?(?)に減った
? でも、辺の性質上、? の値が小さい頂点から順にそれを
終点とする最短経路を求めていけば、すべての頂点間
の最短距離が?(?2
)で求められる
? おわり

IJPC-2 C問題解説