解説
前提:頂点(マス)と辺(道)で構成されるマップは「グラフ」と呼ばれています。特に、辺に向きがある場合は「有向グラフ」、辺に向きがない場合は「無向グラフ」と呼ばれています。
この問題はダイクストラ法を用いて解くことができます。
ダイクストラ法は、このようなグラフ上で、ある頂点から他の頂点までの最短経路を求めるアルゴリズムです。
しかし、移動回数によって進める道が変化するため、単純にダイクストラ法を適用することはできません。
どうすればよいでしょうか?
有向グラフで「おすすめ」を表現することを考えます。
頂点をそれぞれ個に分割し、それぞれを「から選べるときの頂点」「から選べるときの頂点」...「から選べるときの頂点」とし、
各頂点のおすすめセットに応じて道を追加することで、移動回数によって進める道が変化することを表現できます。
このようにするとダイクストラ法を適用することができます。(よく「頂点倍加」や「拡張ダイクストラ」と呼ばれます。)
入力例2を例にすると、以下のようなグラフを作ることができます。(マスの中は「マスの番号 / おすすめセットの番号」、矢印の中は道を進むのに選ぶ曲の難易度の最小値です。)
解答は「 / 」、「 / 」、...、「 / 」の中で最小のものになります。
計算量はであり、十分に高速です。
ユーザー解説
ユーザー解説を書くユーザー解説はまだありません。