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

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

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

По схеме дороги имеют длины:

• $$A C = 40$$
• $$C B = 60$$
• $$A B = 40$$
• $$A E = 80$$
• $$E D = 50$$
• $$D B = 10$$

Проверим основные пары:

• $$A D: \; A \to B \to D = 40 + 10 = 50$$, а через $$E$$: $$80 + 50 = 130$$. Кратчайшее расстояние: $$50$$.
• $$C D: \; C \to B \to D = 60 + 10 = 70$$, через $$A$$ и $$E$$: $$40 + 80 + 50 = 170$$. Кратчайшее расстояние: $$70$$.
• $$B E: \; B \to D \to E = 10 + 50 = 60$$, через $$A$$: $$40 + 80 = 120$$. Кратчайшее расстояние: $$60$$.
• $$C E: \; C \to A \to E = 40 + 80 = 120$$, через $$B$$ и $$D$$: $$60 + 10 + 50 = 120$$. Кратчайшее расстояние: $$120$$.

Наибольшее из полученных кратчайших расстояний равно $$120$$.

Ответ: 1