AOJ2200: Mr. Rito Post Office

Mr. Rito Post Office | Aizu Online Judge

解き方

• からへの行き方は次の2通り
  • 陸路で行く
  • 船のあるところまで陸路で行き、船で適当なところまで行き、再度陸路
• 前計算として、陸路での最短距離、海路での最短距離をWarshall Floydで求めておく
• dp[i][j] = 船がjにある状態でz_iまで集配するための最短距離として動的計画法
  • dp[0][z_0] = 0、その他INFが初期状態
  • [tex:O(RN²)]は間に合うか怪しいと思ったが、間に合った

ハマったところ

• Warshall Floydまでは思いついたが、直前の船の位置だけメモ化すればよいことに気づかず、しばらくO(R^N)の解法しか思いつかなかった

github.com