2014-川上り-解説
- 正解は「スタート → B → C → D → E → ゴール」です。
- 「スタート → A → C → E → ゴール」は2+5+5+5=17の体力を消費します。
- 「スタート → A → C → E → D → ゴール」は2+5+5+2+3+5=22の体力を消費します。
- 「スタート → B → C → D → E → ゴール」は3+3+2+2+5=15の体力を消費します。（最も小さいので正解です）
- 「スタート → B → C → D → ゴール」は3+3+2+3+5=16の体力を消費します。
- 試してみよう
- どの順番で移動すると，どのように体力を消費するか試してみよう。
- 解説
- スタートとゴールと A から E の7箇所の地点と，それらの間を移動できる９本の川の区間は，点と線によるグラフ構造で表すことができます。川の区間上にある通過すると体力を消費する障害物は，その区間の距離とみなせます。この問題では，スタートからゴールまでの最短経路を求めます。（実際には，距離が15以下の経路を見つけます。）
- 線に距離が決められたグラフ上で2点間を結ぶ最短経路を求めるアルゴリズムは，最短時間の移動経路や最も安く移動できる経路の探索などに利用されています。
- 出題国: この問題は日本で作成されました。
注があるものを除き, このサイトの内容物は
