В общую длину пути будет входить длина пути AC = 10
Длина пути напрямую из C в F (CF) = 8.
Нам нужно проверить, если ли смысл ехать в другой нас. пункт из C, чтоб сократить общий путь.
Варианты, где расстояние из C в другой нас. пункт больше или равно CF отбрасываем. У нас остаются:
CB = 6CD = 2 CE = 5Теперь проверим, из какого из этих пунктов расстояние в F не превышает расстояние CF - 8.
BF = 1DF = 4EF = 0Найдем общий размер пути, который нужно преодолеть с самого начала и найдем меньший
ACF = 10 + 8 = 18ACBF = 10 + 6 + 1 = 17ACDF = 10 + 2 + 4 = 16ACEF = 10 + 5 + 0 = 15Длина кратчайшего пути между пунктами А и F, проходящая через пункт С = 15 (ACEF).
В общую длину пути будет входить длина дороги AC = 10
Длина пути напрямую из C в F (CF) = 8.
Нам нужно проверить, если ли смысл ехать в другой нас. пункт из C, чтоб сократить общий путь.
Варианты, где расстояние из C в другой нас. пункт больше или равно CF отбрасываем. У нас остаются:
CB = 6CD = 2CE = 5Теперь проверим, из какого из этих пунктов расстояние в F не превышает расстояние CF - 8.
BF = 1DF = 4EF = 0Подсчитаем общий размер пути, который нужно преодолеть с самого начала и найдем наименьший
ACF = 10 + 8 = 18ACBF = 10 + 6 + 1 = 17ACDF = 10 + 2 + 4 = 16ACEF = 10 + 5 + 0 = 15Длина кратчайшего пути между пунктами А и F, проходящая через пункт С = 15 (ACEF).
// Внимание! Если программа не работает, обновите версию!
begin
var n:=15;
var a:=ArrRandom(n,-99,99); a.Println;
Range(2,n,2).Select(t->a[t-1]).Println
end.
Пример
21 -19 -93 -18 -16 -58 -91 21 -74 85 -60 -16 68 31 72
-19 -18 -58 21 85 -16 31