続き

会社のお昼休みに問題ＤとＥを考えた．
問題Ｄは，やっぱりダイクストラでいく．昨日は，チケットの使用順序を固定しても，チケットの使用状況が異なるから，単純な距離比較は出来ないってところで終わった．だったら，使用状況別に距離比較をすれば良いんじゃないか．
すなわち，ダイクストラだと各ノードはその時点での最短距離を持っているんだけど，最短距離をチケット使用状況別に分けて比較すればよい．チケット使用状況は，使った・使ってないの２の８乗＝２５６種しか存在しないから，ノードに２５６種類の距離の値を持たせて置けばよい．
で，ダイクストラのアルゴリズムを改変して，あるノードの距離の値をチェックするときに，使ってないチケットを使うとどうなるかってのを計算して，２５６種の距離の値を更新していけば良いんじゃないだろうか．
ついでに，この方法だとチケットの使用順序を固定する必要もなくなるから，１回の探索で求まることになる．
う〜ん，出来そうな気がしてきた．
問題Ｅは，シミュレーションは止め．解析的に解く（解けるかも）．
まず，ロボットＡとロボットＢが動く軌跡において，通信を行うことが出来るかどうか，出来るならばその時刻の区間は何時から何時までかを調べる．どうやって調べるかというと，各時刻区間のロボットの座標(x,y)は，時刻tを媒介変数とした数式によって表すことが出来る．で，(x-x')^2 + (y-y')^2 < R^2の式に代入して，tに関する２次不等式を作る．この不等式が，数式が成立するtの区間において２次不等式が成り立つtの区間を求める．で，これを時刻0から最終時刻まで全ての区間において調べる．すると，ロボットＡとロボットＢが通信を行える時刻の区間の集合を求めることが出来る．
それが求まったら，各ロボットが最も早く情報を仕入れる時刻を，その区間を頼りに求めていけば，最終的にどのロボットが情報を仕入れることが出来るかを調べられる．
問題ＤとＥについては，これでどうだろう．なんとなく解けそうな気がしてきたので，今夜にでも酒のつまみに実装してみる．

追記

問題Ｄ，この方法だとダイクストラじゃダメだったねorz
各ノードのチケット使用方法による距離の値が収束するまで近隣のノードと値を計算していかないといけないorz
ほとんど全探査やんけ．
結論．どうせ全探査やるんだったら，やっぱり一番得意するバックトラックに切り替えます．

追記２

う〜ん，バックトラックの全探査にしたらすぐにプログラムが書けた．しかも動いたorz
４年前の経験が活かされてない罠．余計なこと（カッコイイこと）は考えない．とにかく，動くものを作る．すっかり忘れてたよ．
で，実装したアルゴリズムだけど，こんな感じ．ちなみに，入出力は省いているから．

public void search( int current, int usage, int weights, double distances, int[] tickets ){
    for( int i=0; i nd ){
                        distances[i][nu] = nd;
                        search( i, nu, weights, distances, tickets );
                    }
                }
            }
        }
    }
}

簡単に説明すると，引数はそれぞれ，現在位置，使用したチケットのフラグ，各ノード間の距離，各ノードまでのチケット使用状況における最短距離，チケットの内容．

全ての都市iに対して繰り返す．
　もし，iが現在位置ならばスルー．
　もし現在位置からiまで接続されているならば，
　　全てのチケットkについて繰り返す．
　　　kが使用済みでなければ，
　　　　kを使用済みとしたときのチケットの使用状況をnuとする．
　　　　kを使用してiへ移動したときのスタート地点からの距離をndとする．
　　　　もし，ndがkを使う前よりも小さければ，
　　　　　iへの最短距離をndとする．
　　　　　iを現在位置，チケットの使用状況をnuとして再帰的に繰り返す．

なお，distancesが再帰中にがんがん変更されるのは仕様です．