「分かりそう」で「分からない」でも「分かった」気になれるIT用語辞典

問題

問題文
地点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
ピヨ意訳：Xから出発してA、B、Cを全部通ってYに行くよ。所要時間は以下の図と表のとおりだよ。XからYまで最短何分で行ける？ちなみに、A、B、Cは、どんな順番で通ってもいいよ。 単位　分 終点 A B C Y 始点 X 20 20 40 不可 A - 40 30 不可 B 40 - 20 60 C 30 20 - 60

正解

ピヨピヨ解説

図と表を見比べて地道に数えていけば解けます。

まず、A、B、Cを全部通ってXからYに行くルートは以下の6通りあります。

１．X → A → B → C → Y
２．X → A → C → B → Y
３．X → B → A → C → Y
４．X → B → C → A → B or C → Y
５．X → C → A → B → Y
６．X → C → B → A → B or C → Y

４と６は多分、最短にはならないでしょう。
BもしくはCを1回多く通りますからね。
消してしまいます。
残るは

１．X → A → B → C → Y
２．X → A → C → B → Y
３．X → B → A → C → Y
５．X → C → A → B → Y

の4つです。

次に、表と見比べて、それぞれのルートの所要時間を計算します。
さくっと計算すると、以下のようになります。

１．X 【20】 A 【40】 B 【20】 C 【60】 Y ＝ 140
２．X 【20】 A 【30】 C 【20】 B 【60】 Y ＝ 130
３．X 【20】 B 【40】 A 【30】 C 【60】 Y ＝ 150
５．X 【40】 C 【30】 A 【40】 B 【60】 Y ＝ 170

どうやら

２．X 【20】 A 【30】 C 【20】 B 【60】 Y ＝ 130

が一番短いですね。

２．X → A → C → B → Y

のルートが所要時間「130分」で一番短いと分かりました。
「イ：130」が正解です。