На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. В таблице в левом столбце указаны номера пунктов, откуда совершается движение, в первой строке – куда. Определите длину кратчайшего маршрута между пунктами Г и З. Передвигаться можно только по указанным дорогам.
| |
П1 |
П2 |
П3 |
П4 |
П5 |
П6 |
П7 |
П8 |
| П1 |
|
1 |
|
5 |
4 |
|
|
|
| П2 |
1 |
|
|
|
2 |
|
|
|
| П3 |
|
|
|
10 |
|
|
2 |
2 |
| П4 |
5 |
|
10 |
|
9 |
|
|
|
| П5 |
4 |
2 |
|
9 |
|
1 |
|
|
| П6 |
|
|
|
|
1 |
|
|
2 |
| П7 |
|
|
2 |
|
|
|
|
2 |
| П8 |
|
|
2 |
|
|
2 |
2 |
|
|
![]()
.png)