Анализировать простейшие модели объектов · 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 | 2 | 1 | 5 | ||
B | 2 | 4 | |||
C | 1 | 4 | 1 | 4 | |
D | 1 | 2 | |||
E | 5 | 4 | 2 |
Определите длину кратчайшего пути между пунктами B и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Правильный ответ
6
Пояснение
Решение. Для решения этой задачи мы построим дерево всех возможных путей из пункта B в пункт E, чтобы найти самый короткий из них. Согласно условию, каждый пункт можно посетить не более одного раза.
Выпишем все возможные маршруты, начиная из пункта B:
1) Путь B — A (длина 2):
— Из A можно пойти в C: B — A — C (длина 2+1=3).
— Из C можно пойти в D: B — A — C — D (длина 3+1=4). Из D можно пойти в E: B — A — C — D — E. Длина: 4+2=6.
— Из C можно пойти в E: B — A — C — E. Длина: 3+4=7.
— Из A можно пойти в E напрямую: B — A — E. Длина: 2+5=7.
2) Путь B — C (длина 4):
— Из C можно пойти в A: B — C — A (длина 4+1=5). Из A можно пойти в E: B — C — A — E. Длина: 5+5=10.
— Из C можно пойти в D: B — C — D (длина 4+1=5). Из D можно пойти в E: B — C — D — E. Длина: 5+2=7.
— Из C можно пойти в E напрямую: B — C — E. Длина: 4+4=8.
Теперь сравним длины всех найденных маршрутов:
1. B — A — C — D — E: 6 км.
2. B — A — C — E: 7 км.
3. B — A — E: 7 км.
4. B — C — A — E: 10 км.
5. B — C — D — E: 7 км.
6. B — C — E: 8 км.
Самым коротким является путь B — A — C — D — E, его длина составляет 6 км.
Ответ: 6
Источник: ФИПИ