D別解

本体サイトのほうで、D問題、馬券の使い方を固定してその8!に対して
ダイクストラを最初に思いついたが、馬券を固定してのダイクストラが分からなかった、
見たいな事を書いたが、今さっき思いついてしまった。
ある地点までにある枚数を使ったその時点での最短経路が
その先も考えた場合に最短になるか分からない、
と言うのが出来ないと判断した主な理由であるが、
最短になるかどうか分からないのであれば、
馬券を使った枚数ごとに別々に全部最短距離を覚えておけばいいことに気づいた。
まぁ、これもグラフを拡張してのダイクストラと言えるだろうか。
計算量だが、このダイクストラを行うのに必要な計算量が
ノード数30*8=240の、エッジ数30*29/2*8=3480で
ヒープを使ったダイクストラで数千ステップ、
さらにこれを8!回行うので全体でおよそ1億ステップか。
なんというか微妙に遅そうだが、我慢すれば間に合いそうな気もする。
でも、上で書いた解法のほうがおそらく良い解法だろう。

また、上ではグラフを拡張して、その上で(普通の)ダイクストラを
走らせるとしているが、ここでグラフを拡張せずに
ダイクストラの方を改造して馬券使用状況別に状態を
扱うことも出来るようだ。
まぁ、これはどっちにしても計算量が変わるわけではないので
どっちがいいとも言いがたいが、グラフの生成がさほど面倒でないのに加え、
ダイクストラが既存のルーチンを使いまわせる分
グラフを拡張したほうが良いのではないだろうか。

さらにもう一つ、探索+枝刈りが間に合ってしまうらしい。
具体的にどうやって探索してどうやって枝刈りをすればいいのかは
分からないが、どうやらそういう話だ。
ただ、枝刈りを考慮しない全探索で全く間に合いそうにないものが
(きっとナイーブには200C8ぐらいの計算量になると思うが)
枝刈りで何とかなるかも知れないとして
そんな博打に打って出るのはうまくない。
よほど時間が切迫してやけっぱちで書くのなら別であるが…。