外部サイトへ移動します

リンク先の URL を確認してから開いてください。

別タブで開く

解説

G - Only World Mode with Ai-Chan

作成者 sevenc_nanashi

テスター unbakedbread

配点 450 点

実行時間制限
2.5 秒
メモリ制限
512 MiB

解説

前提:頂点(マス)と辺(道)で構成されるマップは「グラフ」と呼ばれています。特に、辺に向きがある場合は「有向グラフ」、辺に向きがない場合は「無向グラフ」と呼ばれています。

この問題はダイクストラ法を用いて解くことができます。

ダイクストラ法は、このようなグラフ上で、ある頂点から他の頂点までの最短経路を求めるアルゴリズムです。
しかし、移動回数によって進める道が変化するため、単純にダイクストラ法を適用することはできません。 どうすればよいでしょうか?

有向グラフで「おすすめ」を表現することを考えます。
頂点をそれぞれKK個に分割し、それぞれを「A1A_1から選べるときの頂点」「A2A_2から選べるときの頂点」...「AKA_Kから選べるときの頂点」とし、 各頂点のおすすめセットに応じて道を追加することで、移動回数によって進める道が変化することを表現できます。
このようにするとダイクストラ法を適用することができます。(よく「頂点倍加」や「拡張ダイクストラ」と呼ばれます。)

入力例2を例にすると、以下のようなグラフを作ることができます。(マスの中は「マスの番号 / おすすめセットの番号」、矢印の中は道を進むのに選ぶ曲の難易度の最小値です。)

入力例2

解答は「NN / 11」、「NN / 22」、...、「NN / KK」の中で最小のものになります。

計算量はO(K(N+M)log⁡(NK))O(K(N + M) \log(NK))であり、十分に高速です。

実装例(Ruby、2092ms)

ユーザー解説

ユーザー解説を書く

ユーザー解説はまだありません。