ЕГЭ по информатике 2016. ПК, задание 3

Задание 3. Между населёнными пунктами А, Б, В, Г, Д, Е и К построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

Определите длину кратчайшего пути между пунктами А и К (при условии, что передвигаться можно только по построенным дорогам).

Решение:

1. Построим схему дорог

2. Заметим, что в любой из маршрутов АК входит ребро АБ длиной 5; таким образом, остается найти оптимальный маршрут из Б в К

3. Попробуем перечислить возможные маршруты из Б в К:

Б – В – Д – Г – К длина 11

Б – В – Д – К длина 12

Б – В – Д – Е – К длина 10

Б – Г – К длина 8

Б – Г – Д – К длина 11

Б – Г – Д – Е – К длина 9

Б – Д – Г – К длина 12

Б – Д – К длина 13

Б – Д – Е – К длина 11

4. Из перечисленных маршрутов кратчайший Б – Г – К – имеет длину 8, таким образом общая длина кратчайшего маршрута А – Б – Г – К равна 5 + 8 = 13

Ответ: 13