競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

AOJ2200 Mr. Rito Post Office

ICPC国内予選の過去問ですね
実は去年解いた記憶があります(まあ去年は青コーダーでしたし激遅だったのでいい復習になりました
10分で解きたい問題

解法

あらかじめ,陸路のみ,海路のみの全頂点間最短路についてワーシャルフロイドを使って求めておきます.
どう見ても制約がDPっぽいので,DPでどういう状態を持たせていくかに考えていくと,
(i番目の目的地,船が放置されている位置)の情報を持って,その状態の最短距離を保存しておけばよさそうです.
で,状態の遷移なのですが,

  • 船を放置したまま陸路で次の目的地へ向かう
  • 船まで最短路で移動し,ある地点で船を放置し(海路の最短距離を使う),そこから次の目的地へ陸路を使って移動する

の2パターンだけなので最初に求めた全頂点間最短距離の情報を使えばO(1)で取り出せます

計算量はO(N^3+RN^2)

ソースコード

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1928897#1

TCのレートが黄色で安定するようになってきました