Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице слева. Определи длину кратчайшего пути между пунктами А и C, проходящего через пункт E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.
Найдём путь из A в E, а потом из E в C, длины путей сложим, это и будет ответ.
1) Путь из A в E.
A - B - D - E имеет длину 6.
Остальные пути длиннее: по ребру C-E идти бессмысленно, из A в C за 1 не попасть, а кратчайший путь из A в D очевидно A - B - D (все другие пути явно содержат ребра длины не меньше 3)
2) Путь из E в C.
E - C имеет длину 5.
Остальные длиннее: если из E идти в D, это уже 3, за 2 из D в C точно не попасть.
11
Объяснение:
Карта маршрутов в виде графа во вложении.
Найдём путь из A в E, а потом из E в C, длины путей сложим, это и будет ответ.
1) Путь из A в E.
A - B - D - E имеет длину 6.
Остальные пути длиннее: по ребру C-E идти бессмысленно, из A в C за 1 не попасть, а кратчайший путь из A в D очевидно A - B - D (все другие пути явно содержат ребра длины не меньше 3)
2) Путь из E в C.
E - C имеет длину 5.
Остальные длиннее: если из E идти в D, это уже 3, за 2 из D в C точно не попасть.