AOJ 2200 Mr. Rito Post Office

Jul 3, 2014  

わからなくてぐぐりました。
http://d.hatena.ne.jp/sune2/20120719/1342723320

z[i]からz[i+1]に移動するとき、

陸路のみ  
陸路 → 海路 → 陸路  

のうち、どちらかのタイプの経路を辿る。

この考え方で実装するとうまくいきます。
dp[i][j]に対して、i-1のとき船があった場所をkとし
z[i-1] →(陸路)→ k →(海路)→ j →(陸路)→ z[i]
と進む事で船を場所jに移し自分はz[i]に移動することができます。
k==jのとき、すなわち船を移動させる必要がないときは、
必ずしもkを経由する必要がないのでz[i-1]からz[i]の陸最短路で良い。
これがわからなくて何回かWAくらった。

このエントリーをはてなブックマークに追加