<?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 , $theNumbOf )
{
$waysAndTimes [ ] = [ 'path' => null , 'time' => INF] ;
$time += $paths [ $point ] [ $target ] [ 'time' ] ;
$pathDone [ ] = $target ;
$theNumbOf += 1 ;
$waysAndTimes [ ] = [ 'path' => $pathDone , 'time' => $time ] ;
}
foreach ( $paths [ $point ] as $subTarget => $timeAndBy ) {
list ( 'path and time' => $waysAndTimes [ ] , 'possible ways' => $theNumbOf ) = makeOneMoreStep
( $paths , array_merge ( $pathDone , [ $subTarget ] ) , $time + $paths [ $point ] [ $subTarget ] [ 'time' ] , $subTarget , $target , $theNumbOf ) ;
}
}
return [ 'path and time' => bestPath( $waysAndTimes ) , 'possible ways' => $theNumbOf ] ;
}
function bestPath( $waysAndTimes )
{
$bestTime = INF;
$bestPath = 0 ;
foreach ( $waysAndTimes as $pathNumber => $wayAndTime ) {
if ( $wayAndTime [ 'time' ] < $bestTime ) {
$bestTime = $wayAndTime [ 'time' ] ;
$bestPath = $pathNumber ;
}
}
return $waysAndTimes [ $bestPath ] ;
}
$point = 'pet' ; // Старт
$target = 'nov' ; // Финиш
$pathDone = [ $point ] ;
$time = 0 ;
print_r ( makeOneMoreStep
( $paths , $pathDone , $time , $point , $target , 0 ) ) ; $pathAndTimePossibleWays = makeOneMoreStep( $paths , $pathDone , $time , $point , $target , 0 ) ;
$bestPath = $pathAndTimePossibleWays [ 'path and time' ] [ 'path' ] ;
$bestTime = $pathAndTimePossibleWays [ 'path and time' ] [ 'time' ] ;
echo "Начальная точка: $pointNames [$point ]" . 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+ICRieVdoYXQpOwp9CgpmdW5jdGlvbiBtYWtlT25lTW9yZVN0ZXAoJHBhdGhzLCAkcGF0aERvbmUsICR0aW1lLCAkcG9pbnQsICR0YXJnZXQsICR0aGVOdW1iT2YpCnsKICAgICR3YXlzQW5kVGltZXNbXSA9IFsncGF0aCcgPT4gbnVsbCwgJ3RpbWUnID0+IElORl07CiAgICBpZiAoYXJyYXlfa2V5X2V4aXN0cygkdGFyZ2V0LCAkcGF0aHNbJHBvaW50XSkpIHsKICAgICAgICAkdGltZSArPSAkcGF0aHNbJHBvaW50XVskdGFyZ2V0XVsndGltZSddOwogICAgICAgICRwYXRoRG9uZVtdID0gJHRhcmdldDsKICAgICAgICAkdGhlTnVtYk9mICs9IDE7CiAgICAgICAgJHdheXNBbmRUaW1lc1tdID0gWydwYXRoJyA9PiAkcGF0aERvbmUsICd0aW1lJyA9PiAkdGltZV07CiAgICB9CiAgICBmb3JlYWNoICgkcGF0aHNbJHBvaW50XSBhcyAkc3ViVGFyZ2V0ID0+ICR0aW1lQW5kQnkpIHsKICAgICAgICBpZiAoIWluX2FycmF5KCRzdWJUYXJnZXQsICRwYXRoRG9uZSkgYW5kICFpbl9hcnJheSgkc3ViVGFyZ2V0LCAkcGF0aERvbmUpKSB7CiAgICAgICAgICAgIGxpc3QoJ3BhdGggYW5kIHRpbWUnID0+ICR3YXlzQW5kVGltZXNbXSwgJ3Bvc3NpYmxlIHdheXMnID0+ICR0aGVOdW1iT2YpID0gbWFrZU9uZU1vcmVTdGVwKCRwYXRocywgYXJyYXlfbWVyZ2UoJHBhdGhEb25lLCBbJHN1YlRhcmdldF0pLCAkdGltZSArICRwYXRoc1skcG9pbnRdWyRzdWJUYXJnZXRdWyd0aW1lJ10sICRzdWJUYXJnZXQsICR0YXJnZXQsICR0aGVOdW1iT2YpOwoKICAgICAgICB9CiAgICB9CiAgICByZXR1cm4gWydwYXRoIGFuZCB0aW1lJyA9PiBiZXN0UGF0aCgkd2F5c0FuZFRpbWVzKSwgJ3Bvc3NpYmxlIHdheXMnID0+ICR0aGVOdW1iT2ZdOwp9CgpmdW5jdGlvbiBiZXN0UGF0aCgkd2F5c0FuZFRpbWVzKQp7CiAgICAkYmVzdFRpbWUgPSBJTkY7CiAgICAkYmVzdFBhdGggPSAwOwogICAgZm9yZWFjaCAoJHdheXNBbmRUaW1lcyBhcyAkcGF0aE51bWJlciA9PiAkd2F5QW5kVGltZSkgewogICAgICAgIGlmICgkd2F5QW5kVGltZVsndGltZSddIDwgJGJlc3RUaW1lKSB7CiAgICAgICAgICAgICRiZXN0VGltZSA9ICR3YXlBbmRUaW1lWyd0aW1lJ107CiAgICAgICAgICAgICRiZXN0UGF0aCA9ICRwYXRoTnVtYmVyOwogICAgICAgIH0KICAgIH0KICAgIHJldHVybiAkd2F5c0FuZFRpbWVzWyRiZXN0UGF0aF07Cn0KCiRwb2ludCA9ICdwZXQnOyAvLyDQodGC0LDRgNGCCiR0YXJnZXQgPSAnbm92JzsgLy8g0KTQuNC90LjRiAokcGF0aERvbmUgPSBbJHBvaW50XTsKJHRpbWUgPSAwOwoKcHJpbnRfcihtYWtlT25lTW9yZVN0ZXAoJHBhdGhzLCAkcGF0aERvbmUsICR0aW1lLCAkcG9pbnQsICR0YXJnZXQsIDApKTsKJHBhdGhBbmRUaW1lUG9zc2libGVXYXlzID0gbWFrZU9uZU1vcmVTdGVwKCRwYXRocywgJHBhdGhEb25lLCAkdGltZSwgJHBvaW50LCAkdGFyZ2V0LCAwKTsKCiRiZXN0UGF0aCA9ICRwYXRoQW5kVGltZVBvc3NpYmxlV2F5c1sncGF0aCBhbmQgdGltZSddWydwYXRoJ107CiRiZXN0VGltZSA9ICRwYXRoQW5kVGltZVBvc3NpYmxlV2F5c1sncGF0aCBhbmQgdGltZSddWyd0aW1lJ107CgplY2hvICLQndCw0YfQsNC70YzQvdCw0Y8g0YLQvtGH0LrQsDogJHBvaW50TmFtZXNbJHBvaW50XSIgLiBQSFBfRU9MOwpmb3IgKCRpID0gMDsgJGkgPCBjb3VudCgkYmVzdFBhdGgpIC0gMTsgJGkrKykgewogICAgJGEgPSAkYmVzdFBhdGhbJGldOwogICAgJGIgPSAkYmVzdFBhdGhbJGkgKyAxXTsKICAgIGVjaG8gItCY0Lcg0L3QtdC1IHskdHJhbnNwb3J0TmFtZVskcGF0aHNbJGFdWyRiXVsnYnknXV19INC00L4g0YLQvtGH0LrQuCB7JHBvaW50TmFtZXNbJGJlc3RQYXRoWyRpKzFdXX0geyRwYXRoc1skYV1bJGJdWyd0aW1lJ119INC80LjQvSIgLiBQSFBfRU9MOwp9CmVjaG8gItCSINC40YLQvtCz0LUg0YLRiyDQv9C+0L/QsNC00LXRiNGMINCyINGC0L7Rh9C60YMgeyRwb2ludE5hbWVzWyRiXX0g0LfQsCB7JGJlc3RUaW1lfSDQvNC40L3Rg9GCICI7