AOJ2200: Mr. Rito Post Office

数日悩んだ結果問題文誤読と気付いたのでキレそうです。

問題概要

陸路と海路を使って指定された順番に村を回っていく最短距離を求めよ。

Mr. Rito Post Office | Aizu Online Judge

解説

取り敢えず最短経路問題なので、真っ先に思い付くのはダイクストラ。持つ情報としては「何番目の村まで訪れたか」「今どこか」「船はどこにあるのか」の3つで、これを全部一気にやるとO(n²rlogn²r)かかり、明らかに無理です。また、ここから「何番目の村まで訪れたか」という情報を固定し、順番にダイクストラをr回実行する、という考え方をすればO(rn²logn)まで落とせます。が間に合いません。

ここで重要なのは、

• z[i]→z[i+1]の移動では、海路は一度のみしか利用する機会がない

という点で、これを使うと、

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

の2パターンの動きのみで行けることが分かります。ここまで考えると、nの制約からワーシャルフロイドを用いることが思い付き、前計算O(n³)、本計算O(rn²)で解けます。（海路の始点、終点でループを回すのでn²かかります）

AIZU ONLINE JUDGE: Code Review

感想

この問題で苦労したのは初期位置で、

利藤さんは，はじめに必ずある港町に船とともにいる．

から「どこから始めてもよい」という解釈をして延々とWAを出して苦しんでいました…入力の制約に書いてある通り、開始位置はz₁で固定です。