Анализировать простейшие модели объектов · 81 задание
- Задание №4№4
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути…
Графы
- Задание №4№4
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего п…
Графы
- Задание №4№4
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути…
Графы
- Задание №4№4
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. Определите длину кратчайшего пути между пункт…
Графы
- Задание №4№4
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего п…
Графы
- Задание №4№4
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути…
Графы
- Задание №4№4
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути…
Графы
- Задание №4№4
Между населёнными пунктами A , B , C , D , E , F построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайш…
Графы
- Задание №4№4
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых приведена в таблице. Определите длину кратчайшего пути между пунктами…
Графы
- Задание №4№4
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути…
Графы
- Задание №4№4
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых приведена в таблице. Определите длину кратчайшего пути между пунктами…
Графы
- Задание №4№4
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути…
Графы
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
A | B | C | D | E | |
A | 7 | 4 | |||
B | 7 | 2 | 5 | ||
C | 4 | 2 | 4 | ||
D | 4 | 5 | |||
E | 5 | 5 |
Определите длину кратчайшего пути между пунктами A и Е. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Правильный ответ
11
Пояснение
Решение.
Для решения этой задачи мы воспользуемся методом перебора всех возможных путей из пункта A в пункт E, учитывая условие, что каждый пункт можно посетить только один раз. Для удобства будем выписывать маршруты и суммировать их длины на основе данных из таблицы.
Посмотрим, какие дороги выходят из начального пункта A:
1. Из A можно попасть в B (длина 7 км).
2. Из A можно попасть в C (длина 4 км).
Теперь проследим все возможные продолжения для каждого варианта:
Вариант 1: Путь через B (A → B ...)
- Из B можно поехать в C: A → B → C (длина 7+2=9 км). Из C можно поехать в D: A → B → C → D (длина 9+4=13 км). Из D можно поехать в E: A → B → C → D → E. Итого: 7+2+4+5=18 км.
- Из B можно поехать сразу в E: A → B → E. Итого: 7+5=12 км.
Вариант 2: Путь через C (A → C ...)
- Из C можно поехать в B: A → C → B (длина 4+2=6 км). Из B можно поехать в E: A → C → B → E. Итого: 4+2+5=11 км.
- Из C можно поехать в D: A → C → D (длина 4+4=8 км). Из D можно поехать в E: A → C → D → E. Итого: 4+4+5=13 км.
Сравним полученные результаты:
1. A → B → C → D → E = 18 км
2. A → B → E = 12 км
3. A → C → B → E = 11 км
4. A → C → D → E = 13 км
Самым коротким оказался путь A → C → B → E, длина которого составляет 11 км.
Ответ: 11 км
Источник: ФИПИ