Задача Задача №1209574
А
А
Иван-Царевич спешит выручить Марью-Царевну из плена Кощея. В таблице указана протяженность дорог между пунктами, через которые он может пройти. Укажите длину самого короткого участка кратчайшего пути от Ивана-Царевича до Марьи Царевны (от точки И до точки М). Передвигаться можно только по дорогам, указанным в таблице: А Б В Г И М А 1 1 Б 2 1 3 В 1 2 Г 6 1 И 1 1 6 8 М 3 1 8
Для поиска самого короткого участка кратчайшего пути от Ивана-Царевича до Марьи-Царевны (от точки И до точки М) можно воспользоваться алгоритмом Дейкстры. Ниже представлена таблица, в которой для каждой точки указана длина кратчайшего пути от точки И:
| Точка | Длина кратчайшего пути от И |
|---|---|
| А | 1 |
| Б | 2 |
| В | 1 |
| Г | 7 |
| И | 0 |
| М | - |
Таким образом, самый короткий участок кратчайшего пути от Ивана-Царевича до Марьи-Царевны равен 8 и проходит через точки И-Б-М.
