В
Все
М
Математика
А
Английский язык
Х
Химия
Э
Экономика
П
Право
И
Информатика
У
Українська мова
Қ
Қазақ тiлi
О
ОБЖ
Н
Немецкий язык
Б
Беларуская мова
У
Українська література
М
Музыка
П
Психология
А
Алгебра
Л
Литература
Б
Биология
М
МХК
О
Окружающий мир
О
Обществознание
И
История
Г
Геометрия
Ф
Французский язык
Ф
Физика
Д
Другие предметы
Р
Русский язык
Г
География
Alena200302
Alena200302
31.05.2023 14:10 •  Информатика

Между населёнными пунктами A, B, C, D, E, F, Z построены дороги с односторонним движением. В таблице указана протяжённость каждой дороги. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет. Например, из A в B есть дорога длиной 4 км, а из B в A дороги нет. Курьеру требуется проехать из A в Z, посетив не менее 6 населённых пунктов. Пункты A и Z при подсчёте учитываются, два раза проходить через один пункт нельзя. Какова наименьшая возможная длина маршрута курьера? В ответе запишите натуральное число – длину минимального маршрута.


Между населёнными пунктами A, B, C, D, E, F, Z построены дороги с односторонним движением. В таблице

Показать ответ
Ответ:
KYRT2
KYRT2
19.11.2020 16:36

22

Объяснение:

Строим граф - картинка 1

считаем пути

ABCDEZ = 4 + 3 + 11 + 4 + 1 = 23

ABCDFZ = 4 + 3 +11 + 3 + 2 = 23

ABCDEFZ = 4 + 3 + 11 + 4 + 4 + 2 = 28

ABCEFZ = 4 + 3 + 10 + 4 + 2 = 23

ABDEFZ = 4 + 8 + 4 + 4 + 2 = 22

ACDEFZ = 6 + 11 + 4 + 4 + 2 = 27

или

Строим дерево - картинка 2 (ветви, которые очевидно не достигают 6 пунктов не строим)

считаем пути


Между населёнными пунктами A, B, C, D, E, F, Z построены дороги с односторонним движением. В таблице
Между населёнными пунктами A, B, C, D, E, F, Z построены дороги с односторонним движением. В таблице
0,0(0 оценок)
Популярные вопросы: Информатика
Полный доступ
Позволит учиться лучше и быстрее. Неограниченный доступ к базе и ответам от экспертов и ai-bota Оформи подписку
logo
Начни делиться знаниями
Вход Регистрация
Что ты хочешь узнать?
Спроси ai-бота