AOJ 2200 : Mr. リトー郵便局

Mr. Rito Post Office | Aizu Online Judge

船をどこに置いておくかで結果が変わっておきそうなので、
これを状態に持ってDPするのが良さそう。

あらかじめ陸路と海路で分けてワーシャルフロイド法で
各町村間の最短経路を求めておく。

DPするときは船は放っておいて陸路を使い目的地へ移動する遷移と
1~nに今あるところから船を移動させて目的地へ移動する遷移をする。

状態-値はdp[どこに船を置いたか][何番目まで集荷したか] := 最小コスト
で持っておく。

O(M + N^3 + RN^2)

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