Упр.3.173 ГДЗ Сборник упражнений Босова 7-9 класс (Информатика)

Задача

На схеме нарисованы дороги между населенными пунктами А, В, С, D, Е и указаны их протяженности. Определите, какие два населенных пункта наиболее удалены друг от друга (при условии, что передвигаться можно только по указанным на схеме дорогам). В ответе укажите кратчайшее расстояние между этими населенными пунктами (номер верного варианта).

Подробный ответ

Найдём кратчайшие расстояния между всеми парами населённых пунктов, между которыми путь может быть не прямым, а через другие пункты.

Пара пунктов	Возможные пути	Кратчайшее расстояние
A–D	$$A \to E \to D = 80 + 50 = 130$$	$$130$$
C–D	$$C \to A \to E \to D = 40 + 80 + 50 = 170$$ $$C \to B \to D = 60 + 10 = 70$$ $$C \to A \to B \to D = 40 + 40 + 10 = 90$$	$$70$$
B–E	$$B \to D \to E = 10 + 50 = 60$$ $$B \to A \to E = 40 + 80 = 120$$	$$60$$
C–E	$$C \to A \to E = 40 + 80 = 120$$ $$C \to B \to D \to E = 60 + 10 + 50 = 120$$ $$C \to A \to B \to D \to E = 40 + 40 + 10 + 50 = 140$$	$$120$$