<?php
header("Content-Type: text/plain; charset=utf-8");
?>
 
<?php
mb_internal_encoding("UTF-8");
 
error_reporting(-1);
/* http://d...content-available-to-author-only...2.net/ */
 
define('SUBWAY', 'sub');
define('FOOT', 'foot');
define('BUS', 'bus');
 
$transportName = array(
    SUBWAY => 'едешь на метро',
    FOOT => 'идешь пешком',
    BUS => 'едешь на автобусе'
);
 
$startPoint = 'pet'; // Петроградская
$endPoint   = 'teh'; // Новая Голландия
 
$pointNames = array(
    'pet' => 'ст. м. Петроградская',
    'chk' => 'ст. м. Чкаловская',
    'gor' => 'ст. м. Горьковская',
    'spo' => 'ст. м. Спортивная',
    'vas' => 'ст. м. Василеостровская',
    'kre' => 'Петропавловская крепость',
    'let' => 'Летний сад',
    'dvo' => 'Дворцовая площадь',
    'isa' => 'Исакиевский собор',
    'nov' => 'Новая Голландия',
    'ras' => 'Дом Раскольникова',
    'gos' => 'Гостиный Двор',
    'sen' => 'Сенная Площадь',
    'vla' => 'ст. м. Владимирская',
    'vit' => 'Витебский вокзал',
    'teh' => 'Технологический Институт'
);
 
$paths = array(
    'pet' => array(
        'chk' => canGet(10, BUS),
        'gor' => canGet(3, SUBWAY)
    ),
 
    'chk' => array(
        'pet' => canGet(10, BUS),
        'spo' => canGet(3, SUBWAY)
    ),
 
    'gor' => array(
        'pet' => canGet(3, BUS),
        'kre' => canGet(5, FOOT),
        'gos' => canGet(6, SUBWAY)
    ),
 
    'spo' => array(
        'chk' => canGet(3, SUBWAY),
        'vas' => canGet(10, BUS),
        'sen' => canGet(7, SUBWAY)
    ),
 
    'vas' => array(
        'spo' => canGet(10, BUS),
        'gos' => canGet(7, SUBWAY),
        'nov' => canGet(11, FOOT)
    ),
 
    'kre' => array(
        'gor' => canGet(5, FOOT)
    ),
 
    'let' => array(
        'dvo' => canGet(6, FOOT),
        'gos' => canGet(7, FOOT)
    ),
 
    'dvo' => array(
        'isa' => canGet(6, FOOT),
        'gos' => canGet(6, FOOT),
        'let' => canGet(6, FOOT)
    ),
 
    'isa' => array(
        'dvo' => canGet(6, FOOT),
        'nov' => canGet(5, FOOT)
    ),
 
    'nov' => array(
        'vas' => canGet(11, FOOT),
        'isa' => canGet(5, FOOT),
        'ras' => canGet(7, BUS)
    ),
 
    'ras' => array(
        'nov' => canGet(7, BUS),
        'sen' => canGet(3, FOOT)
    ),
 
    'gos' => array(
        'vas' => canGet(7, SUBWAY),
        'sen' => canGet(3, SUBWAY),
        'dvo' => canGet(6, FOOT),
        'gor' => canGet(6, SUBWAY),
        'let' => canGet(7, FOOT),
        'vla' => canGet(7, FOOT)
    ),
 
    'sen' => array(
        'ras' => canGet(3, FOOT),
        'spo' => canGet(7, SUBWAY),
        'gos' => canGet(3, SUBWAY),
        'vla' => canGet(4, SUBWAY),
        'vit' => canGet(2, SUBWAY),
        'teh' => canGet(3, SUBWAY)
    ),
 
    'vla' => array(
        'sen' => canGet(4, SUBWAY),
        'gos' => canGet(7, FOOT),
        'vit' => canGet(3, SUBWAY)
    ),
 
    'vit' => array(
        'sen' => canGet(2, SUBWAY),
        'teh' => canGet(2, SUBWAY),
        'vla' => canGet(3, SUBWAY)
    ),
 
    'teh' => array(
        'sen' => canGet(3, SUBWAY),
        'vit' => canGet(2, SUBWAY)
    )
);
 
/* Чтобы не писать много раз array('time' => ..., 'by' => ...), используем функцию. 
«canGet» переводится как «можно попасть» */
 
function canGet($time, $byWhat)
{
    return array(
        'time' => $time,
        'by' => $byWhat
    );
}
$pathDone     = array();
$time         = 0;
$lowerTime    = 0;
$crossingTime = array();
function makeOneStep($paths, $startPoint, $endPoint, $time, $lowerTime, $pathDone)
{
 
    $pathDone[] = $startPoint;
    $result     = array();
    if (isset($paths[$startPoint][$endPoint])) {
        $pathDone[] = $endPoint;
        $time += $paths[$startPoint][$endPoint]['time'];
        $result['path'] = $pathDone;
        $result['time'] = $time;
        return $result;
 
    }
    $shortest = array();
 
    foreach ($paths[$startPoint] as $stationName => $stationInfo) {
        if (!in_array($stationName, $pathDone)) {
            $time += $paths[$startPoint][$stationName]['time'];
            $newPath = makeOneStep($paths, $stationName, $endPoint, $time, $lowerTime, $pathDone);
            if (!$lowerTime || ($newPath['time'] < $lowerTime)) {
 
                $lowerTime = $newPath['time'];
                $shortest  = $newPath;
            }
 
        }
    }
    $result = $shortest;
 
    return $result;
 
 
}
$path = makeOneStep($paths, $startPoint, $endPoint, $time, $lowerTime, $pathDone);
 
$text = "Маршрут построен: \n";
$i    = 0;
 
foreach ($path['path'] as $station) {
    if ($i == 0) {
        $text .= "Точка отправления:  $pointNames[$station] \n";
        $i++;
        CONTINUE;
    }
    if ($i == count($path['path']) - 1) {
        $text .= "Конечная точка: $pointNames[$station]. \n Затраченное время: {$path['time']}";
 
    } else {
 
        $text .= "$i $pointNames[$station] \n";
        $i++;
    }
}
echo $text;
 

PD9waHAKaGVhZGVyKCJDb250ZW50LVR5cGU6IHRleHQvcGxhaW47IGNoYXJzZXQ9dXRmLTgiKTsKPz4KCjw/cGhwCm1iX2ludGVybmFsX2VuY29kaW5nKCJVVEYtOCIpOwoKZXJyb3JfcmVwb3J0aW5nKC0xKTsKLyogaHR0cDovL2QuLi5jb250ZW50LWF2YWlsYWJsZS10by1hdXRob3Itb25seS4uLjIubmV0LyAqLwoKZGVmaW5lKCdTVUJXQVknLCAnc3ViJyk7CmRlZmluZSgnRk9PVCcsICdmb290Jyk7CmRlZmluZSgnQlVTJywgJ2J1cycpOwoKJHRyYW5zcG9ydE5hbWUgPSBhcnJheSgKICAgIFNVQldBWSA9PiAn0LXQtNC10YjRjCDQvdCwINC80LXRgtGA0L4nLAogICAgRk9PVCA9PiAn0LjQtNC10YjRjCDQv9C10YjQutC+0LwnLAogICAgQlVTID0+ICfQtdC00LXRiNGMINC90LAg0LDQstGC0L7QsdGD0YHQtScKKTsKCiRzdGFydFBvaW50ID0gJ3BldCc7IC8vINCf0LXRgtGA0L7Qs9GA0LDQtNGB0LrQsNGPCiRlbmRQb2ludCAgID0gJ3RlaCc7IC8vINCd0L7QstCw0Y8g0JPQvtC70LvQsNC90LTQuNGPCgokcG9pbnROYW1lcyA9IGFycmF5KAogICAgJ3BldCcgPT4gJ9GB0YIuINC8LiDQn9C10YLRgNC+0LPRgNCw0LTRgdC60LDRjycsCiAgICAnY2hrJyA9PiAn0YHRgi4g0LwuINCn0LrQsNC70L7QstGB0LrQsNGPJywKICAgICdnb3InID0+ICfRgdGCLiDQvC4g0JPQvtGA0YzQutC+0LLRgdC60LDRjycsCiAgICAnc3BvJyA9PiAn0YHRgi4g0LwuINCh0L/QvtGA0YLQuNCy0L3QsNGPJywKICAgICd2YXMnID0+ICfRgdGCLiDQvC4g0JLQsNGB0LjQu9C10L7RgdGC0YDQvtCy0YHQutCw0Y8nLAogICAgJ2tyZScgPT4gJ9Cf0LXRgtGA0L7Qv9Cw0LLQu9C+0LLRgdC60LDRjyDQutGA0LXQv9C+0YHRgtGMJywKICAgICdsZXQnID0+ICfQm9C10YLQvdC40Lkg0YHQsNC0JywKICAgICdkdm8nID0+ICfQlNCy0L7RgNGG0L7QstCw0Y8g0L/Qu9C+0YnQsNC00YwnLAogICAgJ2lzYScgPT4gJ9CY0YHQsNC60LjQtdCy0YHQutC40Lkg0YHQvtCx0L7RgCcsCiAgICAnbm92JyA9PiAn0J3QvtCy0LDRjyDQk9C+0LvQu9Cw0L3QtNC40Y8nLAogICAgJ3JhcycgPT4gJ9CU0L7QvCDQoNCw0YHQutC+0LvRjNC90LjQutC+0LLQsCcsCiAgICAnZ29zJyA9PiAn0JPQvtGB0YLQuNC90YvQuSDQlNCy0L7RgCcsCiAgICAnc2VuJyA9PiAn0KHQtdC90L3QsNGPINCf0LvQvtGJ0LDQtNGMJywKICAgICd2bGEnID0+ICfRgdGCLiDQvC4g0JLQu9Cw0LTQuNC80LjRgNGB0LrQsNGPJywKICAgICd2aXQnID0+ICfQktC40YLQtdCx0YHQutC40Lkg0LLQvtC60LfQsNC7JywKICAgICd0ZWgnID0+ICfQotC10YXQvdC+0LvQvtCz0LjRh9C10YHQutC40Lkg0JjQvdGB0YLQuNGC0YPRgicKKTsKCiRwYXRocyA9IGFycmF5KAogICAgJ3BldCcgPT4gYXJyYXkoCiAgICAgICAgJ2NoaycgPT4gY2FuR2V0KDEwLCBCVVMpLAogICAgICAgICdnb3InID0+IGNhbkdldCgzLCBTVUJXQVkpCiAgICApLAogICAgCiAgICAnY2hrJyA9PiBhcnJheSgKICAgICAgICAncGV0JyA9PiBjYW5HZXQoMTAsIEJVUyksCiAgICAgICAgJ3NwbycgPT4gY2FuR2V0KDMsIFNVQldBWSkKICAgICksCiAgICAKICAgICdnb3InID0+IGFycmF5KAogICAgICAgICdwZXQnID0+IGNhbkdldCgzLCBCVVMpLAogICAgICAgICdrcmUnID0+IGNhbkdldCg1LCBGT09UKSwKICAgICAgICAnZ29zJyA9PiBjYW5HZXQoNiwgU1VCV0FZKQogICAgKSwKICAgIAogICAgJ3NwbycgPT4gYXJyYXkoCiAgICAgICAgJ2NoaycgPT4gY2FuR2V0KDMsIFNVQldBWSksCiAgICAgICAgJ3ZhcycgPT4gY2FuR2V0KDEwLCBCVVMpLAogICAgICAgICdzZW4nID0+IGNhbkdldCg3LCBTVUJXQVkpCiAgICApLAogICAgCiAgICAndmFzJyA9PiBhcnJheSgKICAgICAgICAnc3BvJyA9PiBjYW5HZXQoMTAsIEJVUyksCiAgICAgICAgJ2dvcycgPT4gY2FuR2V0KDcsIFNVQldBWSksCiAgICAgICAgJ25vdicgPT4gY2FuR2V0KDExLCBGT09UKQogICAgKSwKICAgIAogICAgJ2tyZScgPT4gYXJyYXkoCiAgICAgICAgJ2dvcicgPT4gY2FuR2V0KDUsIEZPT1QpCiAgICApLAogICAgCiAgICAnbGV0JyA9PiBhcnJheSgKICAgICAgICAnZHZvJyA9PiBjYW5HZXQoNiwgRk9PVCksCiAgICAgICAgJ2dvcycgPT4gY2FuR2V0KDcsIEZPT1QpCiAgICApLAogICAgCiAgICAnZHZvJyA9PiBhcnJheSgKICAgICAgICAnaXNhJyA9PiBjYW5HZXQoNiwgRk9PVCksCiAgICAgICAgJ2dvcycgPT4gY2FuR2V0KDYsIEZPT1QpLAogICAgICAgICdsZXQnID0+IGNhbkdldCg2LCBGT09UKQogICAgKSwKICAgIAogICAgJ2lzYScgPT4gYXJyYXkoCiAgICAgICAgJ2R2bycgPT4gY2FuR2V0KDYsIEZPT1QpLAogICAgICAgICdub3YnID0+IGNhbkdldCg1LCBGT09UKQogICAgKSwKICAgIAogICAgJ25vdicgPT4gYXJyYXkoCiAgICAgICAgJ3ZhcycgPT4gY2FuR2V0KDExLCBGT09UKSwKICAgICAgICAnaXNhJyA9PiBjYW5HZXQoNSwgRk9PVCksCiAgICAgICAgJ3JhcycgPT4gY2FuR2V0KDcsIEJVUykKICAgICksCiAgICAKICAgICdyYXMnID0+IGFycmF5KAogICAgICAgICdub3YnID0+IGNhbkdldCg3LCBCVVMpLAogICAgICAgICdzZW4nID0+IGNhbkdldCgzLCBGT09UKQogICAgKSwKICAgIAogICAgJ2dvcycgPT4gYXJyYXkoCiAgICAgICAgJ3ZhcycgPT4gY2FuR2V0KDcsIFNVQldBWSksCiAgICAgICAgJ3NlbicgPT4gY2FuR2V0KDMsIFNVQldBWSksCiAgICAgICAgJ2R2bycgPT4gY2FuR2V0KDYsIEZPT1QpLAogICAgICAgICdnb3InID0+IGNhbkdldCg2LCBTVUJXQVkpLAogICAgICAgICdsZXQnID0+IGNhbkdldCg3LCBGT09UKSwKICAgICAgICAndmxhJyA9PiBjYW5HZXQoNywgRk9PVCkKICAgICksCiAgICAKICAgICdzZW4nID0+IGFycmF5KAogICAgICAgICdyYXMnID0+IGNhbkdldCgzLCBGT09UKSwKICAgICAgICAnc3BvJyA9PiBjYW5HZXQoNywgU1VCV0FZKSwKICAgICAgICAnZ29zJyA9PiBjYW5HZXQoMywgU1VCV0FZKSwKICAgICAgICAndmxhJyA9PiBjYW5HZXQoNCwgU1VCV0FZKSwKICAgICAgICAndml0JyA9PiBjYW5HZXQoMiwgU1VCV0FZKSwKICAgICAgICAndGVoJyA9PiBjYW5HZXQoMywgU1VCV0FZKQogICAgKSwKICAgIAogICAgJ3ZsYScgPT4gYXJyYXkoCiAgICAgICAgJ3NlbicgPT4gY2FuR2V0KDQsIFNVQldBWSksCiAgICAgICAgJ2dvcycgPT4gY2FuR2V0KDcsIEZPT1QpLAogICAgICAgICd2aXQnID0+IGNhbkdldCgzLCBTVUJXQVkpCiAgICApLAogICAgCiAgICAndml0JyA9PiBhcnJheSgKICAgICAgICAnc2VuJyA9PiBjYW5HZXQoMiwgU1VCV0FZKSwKICAgICAgICAndGVoJyA9PiBjYW5HZXQoMiwgU1VCV0FZKSwKICAgICAgICAndmxhJyA9PiBjYW5HZXQoMywgU1VCV0FZKQogICAgKSwKICAgIAogICAgJ3RlaCcgPT4gYXJyYXkoCiAgICAgICAgJ3NlbicgPT4gY2FuR2V0KDMsIFNVQldBWSksCiAgICAgICAgJ3ZpdCcgPT4gY2FuR2V0KDIsIFNVQldBWSkKICAgICkKKTsKCi8qINCn0YLQvtCx0Ysg0L3QtSDQv9C40YHQsNGC0Ywg0LzQvdC+0LPQviDRgNCw0LcgYXJyYXkoJ3RpbWUnID0+IC4uLiwgJ2J5JyA9PiAuLi4pLCDQuNGB0L/QvtC70YzQt9GD0LXQvCDRhNGD0L3QutGG0LjRji4gCsKrY2FuR2V0wrsg0L/QtdGA0LXQstC+0LTQuNGC0YHRjyDQutCw0LogwqvQvNC+0LbQvdC+INC/0L7Qv9Cw0YHRgtGMwrsgKi8KCmZ1bmN0aW9uIGNhbkdldCgkdGltZSwgJGJ5V2hhdCkKewogICAgcmV0dXJuIGFycmF5KAogICAgICAgICd0aW1lJyA9PiAkdGltZSwKICAgICAgICAnYnknID0+ICRieVdoYXQKICAgICk7Cn0KJHBhdGhEb25lICAgICA9IGFycmF5KCk7CiR0aW1lICAgICAgICAgPSAwOwokbG93ZXJUaW1lICAgID0gMDsKJGNyb3NzaW5nVGltZSA9IGFycmF5KCk7CmZ1bmN0aW9uIG1ha2VPbmVTdGVwKCRwYXRocywgJHN0YXJ0UG9pbnQsICRlbmRQb2ludCwgJHRpbWUsICRsb3dlclRpbWUsICRwYXRoRG9uZSkKewogICAgCiAgICAkcGF0aERvbmVbXSA9ICRzdGFydFBvaW50OwogICAgJHJlc3VsdCAgICAgPSBhcnJheSgpOwogICAgaWYgKGlzc2V0KCRwYXRoc1skc3RhcnRQb2ludF1bJGVuZFBvaW50XSkpIHsKICAgICAgICAkcGF0aERvbmVbXSA9ICRlbmRQb2ludDsKICAgICAgICAkdGltZSArPSAkcGF0aHNbJHN0YXJ0UG9pbnRdWyRlbmRQb2ludF1bJ3RpbWUnXTsKICAgICAgICAkcmVzdWx0WydwYXRoJ10gPSAkcGF0aERvbmU7CiAgICAgICAgJHJlc3VsdFsndGltZSddID0gJHRpbWU7CiAgICAgICAgcmV0dXJuICRyZXN1bHQ7CiAgICAgICAgCiAgICB9CiAgICAkc2hvcnRlc3QgPSBhcnJheSgpOwogICAgCiAgICBmb3JlYWNoICgkcGF0aHNbJHN0YXJ0UG9pbnRdIGFzICRzdGF0aW9uTmFtZSA9PiAkc3RhdGlvbkluZm8pIHsKICAgICAgICBpZiAoIWluX2FycmF5KCRzdGF0aW9uTmFtZSwgJHBhdGhEb25lKSkgewogICAgICAgICAgICAkdGltZSArPSAkcGF0aHNbJHN0YXJ0UG9pbnRdWyRzdGF0aW9uTmFtZV1bJ3RpbWUnXTsKICAgICAgICAgICAgJG5ld1BhdGggPSBtYWtlT25lU3RlcCgkcGF0aHMsICRzdGF0aW9uTmFtZSwgJGVuZFBvaW50LCAkdGltZSwgJGxvd2VyVGltZSwgJHBhdGhEb25lKTsKICAgICAgICAgICAgaWYgKCEkbG93ZXJUaW1lIHx8ICgkbmV3UGF0aFsndGltZSddIDwgJGxvd2VyVGltZSkpIHsKICAgICAgICAgICAgICAgIAogICAgICAgICAgICAgICAgJGxvd2VyVGltZSA9ICRuZXdQYXRoWyd0aW1lJ107CiAgICAgICAgICAgICAgICAkc2hvcnRlc3QgID0gJG5ld1BhdGg7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgCiAgICAgICAgfQogICAgfQogICAgJHJlc3VsdCA9ICRzaG9ydGVzdDsKICAgIAogICAgcmV0dXJuICRyZXN1bHQ7CiAgICAKICAgIAp9CiRwYXRoID0gbWFrZU9uZVN0ZXAoJHBhdGhzLCAkc3RhcnRQb2ludCwgJGVuZFBvaW50LCAkdGltZSwgJGxvd2VyVGltZSwgJHBhdGhEb25lKTsKCiR0ZXh0ID0gItCc0LDRgNGI0YDRg9GCINC/0L7RgdGC0YDQvtC10L06IFxuIjsKJGkgICAgPSAwOwoKZm9yZWFjaCAoJHBhdGhbJ3BhdGgnXSBhcyAkc3RhdGlvbikgewogICAgaWYgKCRpID09IDApIHsKICAgICAgICAkdGV4dCAuPSAi0KLQvtGH0LrQsCDQvtGC0L/RgNCw0LLQu9C10L3QuNGPOiAgJHBvaW50TmFtZXNbJHN0YXRpb25dIFxuIjsKICAgICAgICAkaSsrOwogICAgICAgIENPTlRJTlVFOwogICAgfQogICAgaWYgKCRpID09IGNvdW50KCRwYXRoWydwYXRoJ10pIC0gMSkgewogICAgICAgICR0ZXh0IC49ICLQmtC+0L3QtdGH0L3QsNGPINGC0L7Rh9C60LA6ICRwb2ludE5hbWVzWyRzdGF0aW9uXS4gXG4g0JfQsNGC0YDQsNGH0LXQvdC90L7QtSDQstGA0LXQvNGPOiB7JHBhdGhbJ3RpbWUnXX0iOwogICAgICAgIAogICAgfSBlbHNlIHsKICAgICAgICAKICAgICAgICAkdGV4dCAuPSAiJGkgJHBvaW50TmFtZXNbJHN0YXRpb25dIFxuIjsKICAgICAgICAkaSsrOwogICAgfQp9CmVjaG8gJHRleHQ7Cg==