平成28年 春期 ITパスポート 問33

地点Xから出発してA、B、Cの3地点の全てを経由して地点Yまで行きたい。
各地点間の経路と所要時間が図及び表のとおりであるとき、地点Xから地点Yまで行く最短の時間は何分か。
ここで、3地点A、B、Cはどのような順番で経由してもよいものとする。

単位 分
終点
A B C Y
始点 X 20 20 40 不可
A - 40 30 不可
B 40 - 20 60
C 30 20 - 60

 ア  110
 イ  130
 ウ  140
 エ  150


答え イ


解説
XからA、B、Cを経由してYへ至る経路は幾つかありますがそれぞれの時間を計算すると

なので、最短なのはX→A→C→B→Yの130分(イ)です。


キーワード
・アローダイアグラム

キーワードの解説

戻る 一覧へ 次へ