ABC237 E - Skiing (500)
コンテスト中の考察
楽しさの増減を反転させた物をコストとして辺を張る
最小コストの点は決まったらその後コストが更新されなさそうな雰囲気があるのでダイクストラ法でコストを求める
これは嘘解法だが本番ではACでafter_contestで落ちる
解説の解法
それぞれの広場の標高+楽しさを標高に使う
標高が低い場所に移動する場合、標高が楽しさに変わるかのように扱えるので移動コストは0
標高が高い場所に移動する場合、標高の差だけ和が減少する
負辺が無くなるのでダイクストラ法で最短経路が求まる
$ \max(h_0 - h_i - d_i)が答え
前二項が標高が楽しさに変換された部分、最後の項が高い場所への移動で失われた楽しさの部分