問題78
図中の矢印に記した数値は，各区間の運賃を表す。出発地から目的地までの経路のうち，最も安い総運賃は幾らか。
| ア | 19 |
| イ | 20 |
| ウ | 21 |
| エ | 23 |
解答・解説を見る
解答：イ
- 中継地4,5,6に行くまでの一番安い経路を求める。
- 出発地-(2)→中継地3-(6)→中継地4 運賃( 8)
- 出発地-(2)→中継地3-(8)→中継地5 運賃(10)
- 出発地-(5)→中継地2-(5)→中継地6 運賃(10)
- 次に,中継地4,5,6から目的地までの一番安い経路を求める。
- 中継地4-(10)→中継地7-(4)→目的地 運賃(14)
- 中継地5-( 7)→中継地7-(4)→目的地 運賃(11)
- 中継地6-( 3)→中継地8-(7)→目的地 運賃(10)
- 1と2より一番運賃の安い経路を求めると中継地6を通過する経路が一番安いことが分かる。
出発地-(5)→中継地2-(5)→中継地6-( 3)→中継地8-(7)→目的地 運賃(20)