平成28年度春期 ITパスポート 問33 解説
地点Xから出発してA，B，Cの3地点の全てを経由して地点Yまで行きたい。各地点間の経路と所要時間が図及び表のとおりであるとき，地点Xから地点Yまで行く最短の時間は何分か。ここで，3地点A，B，Cはどのような順番で経由してもよいものとする。
- ア110
- イ130
- ウ140
- エ150
答えを見る
正解 イ130
要点経由順の全パターンの所要時間を足して最小のものを選ぶ
解説
Yへ行けるのはBかCからだけ（どちらも60分）なので、X→（A、B、Cを経由）→B又はC→Yの順路を比べます。
- X→A→C→B→Y：20 + 30 + 20 + 60 = 130［分］
- X→A→B→C→Y：20 + 40 + 20 + 60 = 140［分］
- X→B→A→C→Y：20 + 40 + 30 + 60 = 150［分］
- X→C→A→B→Y：40 + 30 + 40 + 60 = 170［分］
AからYへは直接行けないので、Aで終わる順路は使えません。最短は130分です。ア（110）になる順路はなく、ウ（140）、エ（150）は最短ではありません。