Дана таблица длин дорог между пунктами: нужно найти длину самого короткого маршрута, иногда с условием «через пункт» или «не заезжая в пункт». Часть 1, ответ — число в бланке № 1, 1 балл.
| Часть | 1 |
|---|---|
| Ответ | число в бланке № 1 |
| Баллы | 1 балл |
| Проверяет | умение анализировать простую модель — таблицу дорог между пунктами |
| Сколько времени закладывать | около 3 минут по спецификации ФИПИ |
Условие. Между пунктами A, B, C, D, E построены дороги, их длины в километрах даны в таблице; пустая клетка означает, что прямой дороги нет. Найдите длину кратчайшего пути из A в E. Каждый пункт можно посетить не больше одного раза.
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | 7 | 3 | 12 | ||
| B | 7 | 2 | 4 | ||
| C | 3 | 2 | 8 | 8 | |
| D | 4 | 8 | 1 | ||
| E | 12 | 8 | 1 |
Ответ: 10
Условие.
Лера составила карту дорог между населёнными пунктами.
Между пунктами А, Б, В, Г, Д, Е построены дороги. Длины приведены в таблице (пустая ячейка означает, что прямой дороги нет):
| А | Б | В | Г | Д | Е | |
|---|---|---|---|---|---|---|
| А | 4 | 11 | 10 | 7 | ||
| Б | 4 | 12 | ||||
| В | 11 | 3 | 3 | 12 | ||
| Г | 10 | 3 | 4 | |||
| Д | 3 | 9 | ||||
| Е | 7 | 12 | 12 | 4 | 9 |
Определите длину кратчайшего пути между пунктами Б и Г. Передвигаться можно только по дорогам из таблицы. Каждый пункт можно посетить только один раз.
Решение.
Нужно найти кратчайший путь от Б до Г по таблице.
Алгоритм: перебираем все возможные маршруты (граф маленький, до 6! = 720 вариантов), запоминаем минимум.
Длина кратчайшего пути: 14.
Ответ: 14
Условие.
Денис составил карту дорог между населёнными пунктами.
Между пунктами А, Б, В, Г, Д, Е построены дороги. Длины приведены в таблице (пустая ячейка означает, что прямой дороги нет):
| А | Б | В | Г | Д | Е | |
|---|---|---|---|---|---|---|
| А | 15 | 10 | 2 | |||
| Б | 15 | 15 | ||||
| В | 10 | 11 | 14 | |||
| Г | 11 | 6 | 8 | |||
| Д | 15 | 14 | 6 | 10 | ||
| Е | 2 | 8 | 10 |
Определите длину кратчайшего пути между пунктами Е и Г, проходящего через пункт Б. Передвигаться можно только по дорогам из таблицы. Каждый пункт можно посетить только один раз.
Решение.
Нужно найти такой маршрут Е → … → Г, в котором обязательно встречается Б.
Можно мысленно разбить путь на две части: Е → Б и Б → Г, но не повторять вершины. Перебираем все маршруты, удовлетворяющие условию.
Длина кратчайшего такого пути: 38.
Ответ: 38
Условие.
Гриша нарисовал схему транспортных маршрутов.
Между пунктами A, B, C, D, E, F построены дороги. Длины приведены в таблице (пустая ячейка означает, что прямой дороги нет):
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | 7 | 5 | 6 | 10 | ||
| B | 7 | 14 | 2 | 10 | ||
| C | 5 | 14 | 6 | |||
| D | 6 | 2 | 10 | |||
| E | 10 | |||||
| F | 10 | 6 | 10 |
Определите длину кратчайшего пути между пунктами A и F, не проходящего через пункт C. Передвигаться можно только по дорогам из таблицы. Каждый пункт можно посетить только один раз.
Решение.
В графе исключаем вершину C и все её рёбра, затем ищем кратчайший путь A → F обычным перебором.
Длина кратчайшего пути в этих условиях: 16.
Ответ: 16
Оглавление курса «ОГЭ по информатике» под это задание. Содержание открывается после оплаты.