Задание 3. В таблице приведена протяжённость автомагистралей между соседними населёнными пунктами. Если пересечение строки и столбца пусто, то соответствующие населённые пункты не соединены автомагистралями. Найди номер таблицы, для которой истинно условие «Минимальная протяжённость маршрута от А до Г не больше 4». A Б V Γ A 0 2 3 12 Б 2 0 2 3 V 3 2 0 0 J 12 3 0 0 A Б V Γ A 0 3 4 0 Б 3 0 2 1 V 4 2 0 4 Γ 0 1 4 0 A Б V Γ A 0 1 4 0 Б 1 0 3 11 V 4 3 0 3 Γ 0 11 3 0 A Б V Γ A 0 3 5 0 Б 3 0 3 13 V 5 3 0 3 Γ 0 13 3 0

Ответ: 2

Разбираемся:

• Таблица 1:
  • Прямого пути от А до Г нет.
  • Путь через Б: А → Б → Г = 2 + 3 = 5 (больше 4)
  • Путь через В: А → В → Г = 3 + 0 (нет пути)
• Таблица 2:
  • Прямого пути от А до Г нет.
  • Путь через Б: А → Б → Г = 3 + 1 = 4 (не больше 4).
  • Путь через В: А → В → Г = 4 + 4 = 8 (больше 4)
• Таблица 3:
  • Прямого пути от А до Г нет.
  • Путь через Б: А → Б → Г = 1 + 11 = 12 (больше 4)
  • Путь через В: А → В → Г = 4 + 3 = 7 (больше 4)
• Таблица 4:
  • Прямого пути от А до Г нет.
  • Путь через Б: А → Б → Г = 3 + 13 = 16 (больше 4)
  • Путь через В: А → В → Г = 5 + 3 = 8 (больше 4)

Вторая таблица удовлетворяет условию, так как минимальный путь от А до Г через Б равен 4.

Ответ: 2