Дороги в районе

Задание

На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах).

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова длина дороги из пункта Д в пункт К. В ответе запишите целое число — так, как оно указано в таблице.

𒏏	П1	П2	П3	П4	П5	П6	П7
П1	𒏏			60			45
П2		𒏏	50	20	10
П3		50	𒏏	40		30	25
П4	60	20	40	𒏏	15		55
П5		10		15	𒏏
П6			30			𒏏	35
П7

Решение

Только один узел имеет 5 ребер => К == П4

Только у одной вершины - 3 ребра => Д == П2

Е <-> К==П4, Е <-> Д==П2 => Е == П5

К==П4 <-> Д==П2, Е==П5 <-> Д==П2, В <-> Д==П2 => В == П3

А <-> В==П3 и имеет 2 связи => А == П6

У Б - только 2 соединения => Б == П1

Γ == Π7

Длина К==П4 <-> Д==П2 равна 20

𒏏	П1=Б	П2=Д	П3=В	П4=К	П5=Е	П6=А	П7=Г
П1=Б	𒏏			60			45
П2=Д		𒏏	50	20	10
П3=В		50	𒏏	40		30	25
П4=К	60	20	40	𒏏	15		55
П5=Е		10		15	𒏏
П6=А			30			𒏏	35
П7=Г	45		25	55		35	𒏏

Ответ: 20