森のすいりクラブ

上級・なぞ234

全部の道を見回ろう

道を全部点検して、出発したAへ戻ろう。

ルール

↔の各行は、両方向に通れる別々の道1本。(数字)は通るのにかかる時間だよ。全ての道を少なくとも1回通り、最後はAへ戻るよ。同じ道を何回通ってもよいけれど、そのたびに時間がかかるよ。

同じ道を重複して表示していないよ。たとえばAの↔Bは、BからAへも通れる1本の道。

A

↔B(1)↔C(3)↔D(2)

B

↔C(2)↔D(3)

C

↔D(1)

旅のメモ

出発:A到着:A

図とルールを合わせて考えよう。

手がかり

  1. 全てを見回ってAへ戻る道順の中で、合計時間がいちばん小さいものを考えよう。

この問題で遊ぶ

答えと考え方(ネタバレ注意)

いちばん短い合計時間:14

どうしてこの答えになるの?

  1. 6本を1回ずつ通る時間は1+3+2+2+3+1=12。
  2. どの広場も道が3本なので、各広場で入る回数と出る回数をそろえるには、余分な道が少なくとも2本分必要。どの道も1以上だから合計は14以上。
  3. A→B→C→D→C→A→D→B→Aなら合計14で、全部の道を通って戻れる。したがって最短は14。

この問題を画面で遊ぶにはJavaScriptを有効にしてください。