fc2ブログ



高速バス

2010.01.21 20:26  パソコン甲子園 2009

パソコン甲子園2009 問題08 高速バス


グラフのノード間(バス停間)の最短経路のコストを求める問題です。ただし、チケットを使った場合はノード間を行き来するコストが半分になります。最初に持っているチケットの数、スタート地点、ゴール地点が与えられたときの最短コストを求めなければなりません。

基本的にはダイクストラのアルゴリズムで解きます。ただし、グラフのノードは、与えられたグラフのノードi(バス停)と残りのチケットの枚数kの組になります。つまり、2次元配列D[i][k]に「k枚のチケットを持ちバス停iにいるスタート地点からの最小コスト」をダイクストラのアルゴリズムで記録します。

スポンサーサイト



テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |

この記事へのコメント

コメントを書く


管理人にのみ表示

↑ページトップ

この記事へのトラックバック

この記事にトラックバックする(FC2ブログユーザー)

↑ページトップ