<?php
SUBWAY => 'едешь на метро',
FOOT => 'идешь пешком',
BUS => 'едешь на автобусе'
);
$startPoint = 'pet'; // Петроградская
$endPoint = 'nov'; // Новая Голландия
'pet' => 'ст. м. Петроградская',
'chk' => 'ст. м. Чкаловская',
'gor' => 'ст. м. Горьковская',
'spo' => 'ст. м. Спортивная',
'vas' => 'ст. м. Василеостровская',
'kre' => 'Петропавловская крепость',
'let' => 'Летний сад',
'dvo' => 'Дворцовая площадь',
'isa' => 'Исакиевский собор',
'nov' => 'Новая Голландия',
'ras' => 'Дом Раскольникова',
'gos' => 'Гостиный Двор',
'sen' => 'Сенная Площадь',
'vla' => 'ст. м. Владимирская',
'vit' => 'Витебский вокзал',
'teh' => 'Технологический Институт'
);
'chk' => canGet(10, BUS),
'gor' => canGet(3, SUBWAY)
),
'pet' => canGet(10, BUS),
'spo' => canGet(3, SUBWAY)
),
'pet' => canGet(3, BUS),
'kre' => canGet(5, FOOT),
'gos' => canGet(6, SUBWAY)
),
'chk' => canGet(3, SUBWAY),
'vas' => canGet(10, BUS),
'sen' => canGet(7, SUBWAY)
),
'spo' => canGet(10, BUS),
'gos' => canGet(7, SUBWAY),
'nov' => canGet(11, FOOT)
),
'gor' => canGet(5, FOOT)
),
'dvo' => canGet(6, FOOT),
'gos' => canGet(7, FOOT)
),
'isa' => canGet(6, FOOT),
'gos' => canGet(6, FOOT),
'let' => canGet(6, FOOT)
),
'dvo' => canGet(6, FOOT),
'nov' => canGet(5, FOOT)
),
'vas' => canGet(11, FOOT),
'isa' => canGet(5, FOOT),
'ras' => canGet(7, BUS)
),
'nov' => canGet(7, BUS),
'sen' => canGet(3, FOOT)
),
'vas' => canGet(7, SUBWAY),
'sen' => canGet(3, SUBWAY),
'dvo' => canGet(6, FOOT),
'gor' => canGet(6, SUBWAY),
'let' => canGet(7, FOOT),
'vla' => canGet(7, FOOT)
),
'ras' => canGet(3, FOOT),
'spo' => canGet(7, SUBWAY),
'gos' => canGet(3, SUBWAY),
'vla' => canGet(4, SUBWAY),
'vit' => canGet(2, SUBWAY),
'teh' => canGet(3, SUBWAY)
),
'sen' => canGet(4, SUBWAY),
'gos' => canGet(7, FOOT),
'vit' => canGet(3, SUBWAY)
),
'sen' => canGet(2, SUBWAY),
'teh' => canGet(2, SUBWAY),
'vla' => canGet(3, SUBWAY)
),
'sen' => canGet(3, SUBWAY),
'vit' => canGet(2, SUBWAY)
),
'dvo' => canGet(6, FOOT),
'nov' => canGet(5, FOOT)
),
);
/* Чтобы не писать много раз array('time' => ..., 'by' => ...), используем функцию.
«canGet» переводится как «можно попасть» */
function canGet($time, $byWhat)
{
return array('time' => $time, 'by' => $byWhat); }
function makeOneMoreStep($paths, $pathDone, $time, $point, $target)
{
static $possibleWays, $possibleTimes;
$time += $paths[$point][$target]['time'];
$pathDone[] = $target;
$possibleWays[] = $pathDone;
$possibleTimes[] = $time;
return;
} else {
foreach ($paths[$point] as $subTarget => $timeAndBy) {
makeOneMoreStep
($paths, array_merge($pathDone, [$subTarget]), $time + $paths[$point][$subTarget]['time'], $subTarget, $target); }
}
}
return ['ways' => $possibleWays, 'travel time' => $possibleTimes];
}
$point = 'pet'; // Старт
$target = 'nov'; // Финиш
$pathDone = [$point];
$time = 0;
$target = 'nov';
$waysAndTime = makeOneMoreStep($paths, $pathDone, $time, $point, $target);
$bestTime = min($waysAndTime['travel time']); // Лучшее время $pathNumber = array_keys($waysAndTime['travel time'], $bestTime)[0]; // Ключ лучшего варианта перемещния $bestPath = $waysAndTime['ways'][$pathNumber]; // лучший вариант перемещения
# Вывод пути
echo "Начальная точка: $pointNames[$startPoint]".PHP_EOL;
for($i = 0;$i<count($bestPath)-1;$i++){ $a = $bestPath[$i];
$b = $bestPath[$i+1];
echo "Из нее {$transportName[$paths[$a][$b]['by']]} до точки {$pointNames[$bestPath[$i+1]]} {$paths[$a][$b]['time']} мин".PHP_EOL;
}
echo "В итоге ты попадешь в точку {$pointNames[$b]} за {$bestTime} минут ";
PD9waHAKCmVycm9yX3JlcG9ydGluZygtMSk7CgpkZWZpbmUoJ1NVQldBWScsICdzdWInKTsKZGVmaW5lKCdGT09UJywgJ2Zvb3QnKTsKZGVmaW5lKCdCVVMnLCAnYnVzJyk7CgokdHJhbnNwb3J0TmFtZSA9IGFycmF5KAogICAgU1VCV0FZID0+ICfQtdC00LXRiNGMINC90LAg0LzQtdGC0YDQvicsCiAgICBGT09UID0+ICfQuNC00LXRiNGMINC/0LXRiNC60L7QvCcsCiAgICBCVVMgPT4gJ9C10LTQtdGI0Ywg0L3QsCDQsNCy0YLQvtCx0YPRgdC1JwopOwoKJHN0YXJ0UG9pbnQgPSAncGV0JzsgLy8g0J/QtdGC0YDQvtCz0YDQsNC00YHQutCw0Y8KJGVuZFBvaW50ID0gJ25vdic7IC8vINCd0L7QstCw0Y8g0JPQvtC70LvQsNC90LTQuNGPCgokcG9pbnROYW1lcyA9IGFycmF5KAogICAgJ3BldCcgPT4gJ9GB0YIuINC8LiDQn9C10YLRgNC+0LPRgNCw0LTRgdC60LDRjycsCiAgICAnY2hrJyA9PiAn0YHRgi4g0LwuINCn0LrQsNC70L7QstGB0LrQsNGPJywKICAgICdnb3InID0+ICfRgdGCLiDQvC4g0JPQvtGA0YzQutC+0LLRgdC60LDRjycsCiAgICAnc3BvJyA9PiAn0YHRgi4g0LwuINCh0L/QvtGA0YLQuNCy0L3QsNGPJywKICAgICd2YXMnID0+ICfRgdGCLiDQvC4g0JLQsNGB0LjQu9C10L7RgdGC0YDQvtCy0YHQutCw0Y8nLAogICAgJ2tyZScgPT4gJ9Cf0LXRgtGA0L7Qv9Cw0LLQu9C+0LLRgdC60LDRjyDQutGA0LXQv9C+0YHRgtGMJywKICAgICdsZXQnID0+ICfQm9C10YLQvdC40Lkg0YHQsNC0JywKICAgICdkdm8nID0+ICfQlNCy0L7RgNGG0L7QstCw0Y8g0L/Qu9C+0YnQsNC00YwnLAogICAgJ2lzYScgPT4gJ9CY0YHQsNC60LjQtdCy0YHQutC40Lkg0YHQvtCx0L7RgCcsCiAgICAnbm92JyA9PiAn0J3QvtCy0LDRjyDQk9C+0LvQu9Cw0L3QtNC40Y8nLAogICAgJ3JhcycgPT4gJ9CU0L7QvCDQoNCw0YHQutC+0LvRjNC90LjQutC+0LLQsCcsCiAgICAnZ29zJyA9PiAn0JPQvtGB0YLQuNC90YvQuSDQlNCy0L7RgCcsCiAgICAnc2VuJyA9PiAn0KHQtdC90L3QsNGPINCf0LvQvtGJ0LDQtNGMJywKICAgICd2bGEnID0+ICfRgdGCLiDQvC4g0JLQu9Cw0LTQuNC80LjRgNGB0LrQsNGPJywKICAgICd2aXQnID0+ICfQktC40YLQtdCx0YHQutC40Lkg0LLQvtC60LfQsNC7JywKICAgICd0ZWgnID0+ICfQotC10YXQvdC+0LvQvtCz0LjRh9C10YHQutC40Lkg0JjQvdGB0YLQuNGC0YPRgicKKTsKCiRwYXRocyA9IGFycmF5KAogICAgJ3BldCcgPT4gYXJyYXkoCiAgICAgICAgJ2NoaycgPT4gY2FuR2V0KDEwLCBCVVMpLAogICAgICAgICdnb3InID0+IGNhbkdldCgzLCBTVUJXQVkpCiAgICApLAoKICAgICdjaGsnID0+IGFycmF5KAogICAgICAgICdwZXQnID0+IGNhbkdldCgxMCwgQlVTKSwKICAgICAgICAnc3BvJyA9PiBjYW5HZXQoMywgU1VCV0FZKQogICAgKSwKCiAgICAnZ29yJyA9PiBhcnJheSgKICAgICAgICAncGV0JyA9PiBjYW5HZXQoMywgQlVTKSwKICAgICAgICAna3JlJyA9PiBjYW5HZXQoNSwgRk9PVCksCiAgICAgICAgJ2dvcycgPT4gY2FuR2V0KDYsIFNVQldBWSkKICAgICksCgogICAgJ3NwbycgPT4gYXJyYXkoCiAgICAgICAgJ2NoaycgPT4gY2FuR2V0KDMsIFNVQldBWSksCiAgICAgICAgJ3ZhcycgPT4gY2FuR2V0KDEwLCBCVVMpLAogICAgICAgICdzZW4nID0+IGNhbkdldCg3LCBTVUJXQVkpCiAgICApLAoKICAgICd2YXMnID0+IGFycmF5KAogICAgICAgICdzcG8nID0+IGNhbkdldCgxMCwgQlVTKSwKICAgICAgICAnZ29zJyA9PiBjYW5HZXQoNywgU1VCV0FZKSwKICAgICAgICAnbm92JyA9PiBjYW5HZXQoMTEsIEZPT1QpCiAgICApLAoKICAgICdrcmUnID0+IGFycmF5KAogICAgICAgICdnb3InID0+IGNhbkdldCg1LCBGT09UKQogICAgKSwKCiAgICAnbGV0JyA9PiBhcnJheSgKICAgICAgICAnZHZvJyA9PiBjYW5HZXQoNiwgRk9PVCksCiAgICAgICAgJ2dvcycgPT4gY2FuR2V0KDcsIEZPT1QpCiAgICApLAoKICAgICdkdm8nID0+IGFycmF5KAogICAgICAgICdpc2EnID0+IGNhbkdldCg2LCBGT09UKSwKICAgICAgICAnZ29zJyA9PiBjYW5HZXQoNiwgRk9PVCksCiAgICAgICAgJ2xldCcgPT4gY2FuR2V0KDYsIEZPT1QpCiAgICApLAoKICAgICdpc2EnID0+IGFycmF5KAogICAgICAgICdkdm8nID0+IGNhbkdldCg2LCBGT09UKSwKICAgICAgICAnbm92JyA9PiBjYW5HZXQoNSwgRk9PVCkKICAgICksCgogICAgJ25vdicgPT4gYXJyYXkoCiAgICAgICAgJ3ZhcycgPT4gY2FuR2V0KDExLCBGT09UKSwKICAgICAgICAnaXNhJyA9PiBjYW5HZXQoNSwgRk9PVCksCiAgICAgICAgJ3JhcycgPT4gY2FuR2V0KDcsIEJVUykKICAgICksCgogICAgJ3JhcycgPT4gYXJyYXkoCiAgICAgICAgJ25vdicgPT4gY2FuR2V0KDcsIEJVUyksCiAgICAgICAgJ3NlbicgPT4gY2FuR2V0KDMsIEZPT1QpCiAgICApLAoKICAgICdnb3MnID0+IGFycmF5KAogICAgICAgICd2YXMnID0+IGNhbkdldCg3LCBTVUJXQVkpLAogICAgICAgICdzZW4nID0+IGNhbkdldCgzLCBTVUJXQVkpLAogICAgICAgICdkdm8nID0+IGNhbkdldCg2LCBGT09UKSwKICAgICAgICAnZ29yJyA9PiBjYW5HZXQoNiwgU1VCV0FZKSwKICAgICAgICAnbGV0JyA9PiBjYW5HZXQoNywgRk9PVCksCiAgICAgICAgJ3ZsYScgPT4gY2FuR2V0KDcsIEZPT1QpCiAgICApLAoKICAgICdzZW4nID0+IGFycmF5KAogICAgICAgICdyYXMnID0+IGNhbkdldCgzLCBGT09UKSwKICAgICAgICAnc3BvJyA9PiBjYW5HZXQoNywgU1VCV0FZKSwKICAgICAgICAnZ29zJyA9PiBjYW5HZXQoMywgU1VCV0FZKSwKICAgICAgICAndmxhJyA9PiBjYW5HZXQoNCwgU1VCV0FZKSwKICAgICAgICAndml0JyA9PiBjYW5HZXQoMiwgU1VCV0FZKSwKICAgICAgICAndGVoJyA9PiBjYW5HZXQoMywgU1VCV0FZKQogICAgKSwKCiAgICAndmxhJyA9PiBhcnJheSgKICAgICAgICAnc2VuJyA9PiBjYW5HZXQoNCwgU1VCV0FZKSwKICAgICAgICAnZ29zJyA9PiBjYW5HZXQoNywgRk9PVCksCiAgICAgICAgJ3ZpdCcgPT4gY2FuR2V0KDMsIFNVQldBWSkKICAgICksCgogICAgJ3ZpdCcgPT4gYXJyYXkoCiAgICAgICAgJ3NlbicgPT4gY2FuR2V0KDIsIFNVQldBWSksCiAgICAgICAgJ3RlaCcgPT4gY2FuR2V0KDIsIFNVQldBWSksCiAgICAgICAgJ3ZsYScgPT4gY2FuR2V0KDMsIFNVQldBWSkKICAgICksCgogICAgJ3RlaCcgPT4gYXJyYXkoCiAgICAgICAgJ3NlbicgPT4gY2FuR2V0KDMsIFNVQldBWSksCiAgICAgICAgJ3ZpdCcgPT4gY2FuR2V0KDIsIFNVQldBWSkKICAgICksCiAgICAnaXNhJyA9PiBhcnJheSgKICAgICAgICAnZHZvJyA9PiBjYW5HZXQoNiwgRk9PVCksCiAgICAgICAgJ25vdicgPT4gY2FuR2V0KDUsIEZPT1QpCiAgICApLAoKKTsKCi8qINCn0YLQvtCx0Ysg0L3QtSDQv9C40YHQsNGC0Ywg0LzQvdC+0LPQviDRgNCw0LcgYXJyYXkoJ3RpbWUnID0+IC4uLiwgJ2J5JyA9PiAuLi4pLCDQuNGB0L/QvtC70YzQt9GD0LXQvCDRhNGD0L3QutGG0LjRji4KICAgIMKrY2FuR2V0wrsg0L/QtdGA0LXQstC+0LTQuNGC0YHRjyDQutCw0LogwqvQvNC+0LbQvdC+INC/0L7Qv9Cw0YHRgtGMwrsgKi8KZnVuY3Rpb24gY2FuR2V0KCR0aW1lLCAkYnlXaGF0KQp7CiAgICByZXR1cm4gYXJyYXkoJ3RpbWUnID0+ICR0aW1lLCAnYnknID0+ICRieVdoYXQpOwp9CgpmdW5jdGlvbiBtYWtlT25lTW9yZVN0ZXAoJHBhdGhzLCAkcGF0aERvbmUsICR0aW1lLCAkcG9pbnQsICR0YXJnZXQpCnsKICAgIHN0YXRpYyAkcG9zc2libGVXYXlzLCAkcG9zc2libGVUaW1lczsKICAgIGlmIChhcnJheV9rZXlfZXhpc3RzKCR0YXJnZXQsICRwYXRoc1skcG9pbnRdKSkgewogICAgICAgICR0aW1lICs9ICRwYXRoc1skcG9pbnRdWyR0YXJnZXRdWyd0aW1lJ107CiAgICAgICAgJHBhdGhEb25lW10gPSAkdGFyZ2V0OwoKICAgICAgICAkcG9zc2libGVXYXlzW10gPSAkcGF0aERvbmU7CiAgICAgICAgJHBvc3NpYmxlVGltZXNbXSA9ICR0aW1lOwogICAgICAgIHJldHVybjsKICAgIH0gZWxzZSB7CiAgICAgICAgZm9yZWFjaCAoJHBhdGhzWyRwb2ludF0gYXMgJHN1YlRhcmdldCA9PiAkdGltZUFuZEJ5KSB7CiAgICAgICAgICAgIGlmICghaW5fYXJyYXkoJHN1YlRhcmdldCwgJHBhdGhEb25lKSkgewogICAgICAgICAgICAgICAgbWFrZU9uZU1vcmVTdGVwKCRwYXRocywgYXJyYXlfbWVyZ2UoJHBhdGhEb25lLCBbJHN1YlRhcmdldF0pLCAkdGltZSArICRwYXRoc1skcG9pbnRdWyRzdWJUYXJnZXRdWyd0aW1lJ10sICRzdWJUYXJnZXQsICR0YXJnZXQpOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQogICAgcmV0dXJuIFsnd2F5cycgPT4gJHBvc3NpYmxlV2F5cywgJ3RyYXZlbCB0aW1lJyA9PiAkcG9zc2libGVUaW1lc107Cn0KCiRwb2ludCA9ICdwZXQnOyAvLyDQodGC0LDRgNGCCiR0YXJnZXQgPSAnbm92JzsgLy8g0KTQuNC90LjRiAokcGF0aERvbmUgPSBbJHBvaW50XTsKJHRpbWUgPSAwOwoKJHRhcmdldCA9ICdub3YnOwoKJHdheXNBbmRUaW1lID0gbWFrZU9uZU1vcmVTdGVwKCRwYXRocywgJHBhdGhEb25lLCAkdGltZSwgJHBvaW50LCAkdGFyZ2V0KTsKcHJpbnRfcigkd2F5c0FuZFRpbWUpOwokYmVzdFRpbWUgPSBtaW4oJHdheXNBbmRUaW1lWyd0cmF2ZWwgdGltZSddKTsgLy8g0JvRg9GH0YjQtdC1INCy0YDQtdC80Y8KJHBhdGhOdW1iZXIgPSBhcnJheV9rZXlzKCR3YXlzQW5kVGltZVsndHJhdmVsIHRpbWUnXSwgJGJlc3RUaW1lKVswXTsgLy8g0JrQu9GO0Ycg0LvRg9GH0YjQtdCz0L4g0LLQsNGA0LjQsNC90YLQsCDQv9C10YDQtdC80LXRidC90LjRjwokYmVzdFBhdGggPSAkd2F5c0FuZFRpbWVbJ3dheXMnXVskcGF0aE51bWJlcl07IC8vINC70YPRh9GI0LjQuSDQstCw0YDQuNCw0L3RgiDQv9C10YDQtdC80LXRidC10L3QuNGPCnByaW50X3IoJGJlc3RQYXRoKTsKCiMg0JLRi9Cy0L7QtCDQv9GD0YLQuAplY2hvICLQndCw0YfQsNC70YzQvdCw0Y8g0YLQvtGH0LrQsDogJHBvaW50TmFtZXNbJHN0YXJ0UG9pbnRdIi5QSFBfRU9MOwpmb3IoJGkgPSAwOyRpPGNvdW50KCRiZXN0UGF0aCktMTskaSsrKXsKICAgICRhID0gJGJlc3RQYXRoWyRpXTsKICAgICRiID0gJGJlc3RQYXRoWyRpKzFdOwogICAgZWNobyAi0JjQtyDQvdC10LUgeyR0cmFuc3BvcnROYW1lWyRwYXRoc1skYV1bJGJdWydieSddXX0g0LTQviDRgtC+0YfQutC4IHskcG9pbnROYW1lc1skYmVzdFBhdGhbJGkrMV1dfSB7JHBhdGhzWyRhXVskYl1bJ3RpbWUnXX0g0LzQuNC9Ii5QSFBfRU9MOwp9CmVjaG8gItCSINC40YLQvtCz0LUg0YLRiyDQv9C+0L/QsNC00LXRiNGMINCyINGC0L7Rh9C60YMgeyRwb2ludE5hbWVzWyRiXX0g0LfQsCB7JGJlc3RUaW1lfSDQvNC40L3Rg9GCICI7