Задание №4313. Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.  ABCDEA 14 37B1 25 C42 3 D 353 2E7   2  Определите длину кратчайшего пути между пунктами A и Е, проходящего через пункт С. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.

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

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

 ABCDE
A 14 37
B1 25 
C42 3 
D 353 2
E  2 

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

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


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

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

Источник: Демонстрационная версия ОГЭ–2023
Сообщить об ошибке


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