Задание №2738. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.  ABCDEFA 315B3 237C2 13D31 1E731 2F15 2 Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт C. Передвигаться можно только по дорогам, указанным в таблице. Каждый пункт можно посетить только один раз.

Задание №2738.
Поиск кратчайшего пути. ОГЭ по информатике

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

 ABCDEF
A 315
B3 237
C2 13
D31 1
E731 2
F15 2

Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт C. Передвигаться можно только по дорогам, указанным в таблице. Каждый пункт можно посетить только один раз.

Пояснение:
Изобразим дороги населенных пунктов и протяженность между ними, приведенную в таблице, в виде графа, а затем определим кратчайший путь:


Получаем, что длина кратчайшего пути между пунктами A и F, проходящего через пункт C, составляет 3 + 2 + 1 + 1 + 2 = 9 километров: путь ABCDEF.

Показать ответ

Источник: ФИПИ. Открытый банк тестовых заданий
Сообщить об ошибке


Тест с похожими заданиями