高速バス
2010.01.21 20:26 パソコン甲子園 2009
パソコン甲子園2009 問題08 高速バス
グラフのノード間(バス停間)の最短経路のコストを求める問題です。ただし、チケットを使った場合はノード間を行き来するコストが半分になります。最初に持っているチケットの数、スタート地点、ゴール地点が与えられたときの最短コストを求めなければなりません。
基本的にはダイクストラのアルゴリズムで解きます。ただし、グラフのノードは、与えられたグラフのノードi(バス停)と残りのチケットの枚数kの組になります。つまり、2次元配列D[i][k]に「k枚のチケットを持ちバス停iにいるスタート地点からの最小コスト」をダイクストラのアルゴリズムで記録します。
グラフのノード間(バス停間)の最短経路のコストを求める問題です。ただし、チケットを使った場合はノード間を行き来するコストが半分になります。最初に持っているチケットの数、スタート地点、ゴール地点が与えられたときの最短コストを求めなければなりません。
基本的にはダイクストラのアルゴリズムで解きます。ただし、グラフのノードは、与えられたグラフのノードi(バス停)と残りのチケットの枚数kの組になります。つまり、2次元配列D[i][k]に「k枚のチケットを持ちバス停iにいるスタート地点からの最小コスト」をダイクストラのアルゴリズムで記録します。
スポンサーサイト
| コメント(0) | トラックバック(0) | ↑ページトップ |