Задание №37668 ЕГЭ Информатике

Определим степени вершин: две вершины степени 2 (Ж и Д), две вершины степени 3 (А и В) и три вершины степени 4 (Б, Г и Е), причем вершина Е однозначно определяется как вершина степени 4, которая связана с двумя другими вершинами той же степени 4 (П7).

Для того, чтобы различить оставшиеся вершины, определим длины путей АБЖ, АГД, ВБЖ и ВГД. Мы не знаем, где какой маршрут, но точно знаем, что эти четыре маршрута:

П1 -> П2 -> П4 = 8 + 15 = 23

П1 -> П5 -> П6 = 13 + 18 = 31

П3 -> П2 -> П4 = 12 + 15 = 27

П3 -> П5 -> П6 = 10 + 18 = 28

Из дополнительного условия (длина кратчайшего пути из пункта А в пункт Ж превышает 30 километров) находим, что маршрут АБЖ – второй, так что П1 = А, П5 = Б и П6 = Ж. Тогда П3 = В, П2 = Г, П4 = Д. Кратчайший путь из В в Е можно найти с помощью дерева возможных маршрутов – это будет путь ВГЕ длиной 26.