На рисунке схема дорог Н-ского района изображена в виде графа,
в таблице содержатся данные о протяженности некоторых дорог между
населёнными пунктами (в километрах).
Длина остальных дорог неизвестна и обозначена в таблице звёздочкой.
Так как таблицу и схему рисовали независимо друг от друга, то нумерация
населённых пунктов в таблице никак не связана с буквенными обозначениями на графе.
Определите минимальную известную протяженность пути из города А в город Б,
состоящего ровно из двух дорог.
.png)
| |
П1 |
П2 |
П3 |
П4 |
П5 |
П6 |
| П1 |
|
* |
|
* |
* |
5 |
| П2 |
* |
|
4 |
8 |
|
3 |
| П3 |
|
4 |
|
* |
9 |
7 |
| П4 |
* |
8 |
* |
|
* |
|
| П5 |
* |
|
9 |
* |
|
* |
| П6 |
5 |
3 |
7 |
|
* |
|