次の問題を解決しようとしています。
私たちの銀河系には N 個の惑星があります。異なる惑星間を移動することはできますが、すべての惑星が安全なルートを介して別の惑星に結合されるわけではありません。各ルートには、光年で指定された長さがあります。あなたの仕事は、与えられた一連の惑星 T(ここで 0
入力は、N(惑星の数)、R(惑星間の安全なルートの数)、トリプル ABL 形式の R ルートで構成されます。ここで、A と B は惑星の恒星 ID を表し、L は惑星間の距離を表します。年、T（基地を設置する必要がある惑星の数）、その後に基地を設置する必要がある惑星の ID を表す T 番号が続きます。
常に ID: 0 の惑星から開始します。惑星 0 に基地を設置する必要がある場合とない場合があります。
私は演習問題を解決しようとしましたが、うまくいく解決策を得ることができましたが、遅すぎます。Floyd Warshall アルゴリズムを使用して、グラフ内の任意の 2 つのノード (惑星) 間の最小パスを取得しました。次に、基数を 0 にする必要がある最も近い惑星を見つけ、その経路を計算します。次に、この惑星を「訪れた惑星」のリストに追加し、「対象」の惑星のリストから削除します。このプロセスを最後まで繰り返しますが、今度は、ターゲットの惑星から訪問した任意の惑星に最も近い惑星を見つけようとします (それらの間の移動は無料なので、最後にどこにいたかは気にしません)。次に、距離を追加し、ターゲットから削除し、訪問済みに追加して、必要なすべてのベースを確立するまで続けます。
これは正しい出力を提供しますが、遅すぎます。
改善のためのアイデアはありますか？おそらく、ダイクストラのアルゴリズムのいくつかの変更されたバージョンですか?