<?php
    error_reporting(-1);
    
    define('SUBWAY', 'sub');
    define('FOOT', 'foot');
    define('BUS', 'bus');

    $transportName = array(
        SUBWAY  =>  'едешь на метро',
        FOOT    =>  'идешь пешком',
        BUS     =>  'едешь на автобусе'
    );
     
    $startPoint = 'pet'; // Петроградская
    $endPoint = 'nov'; // Новая Голландия
     
    $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)        
        )
    );

    function canGet($time, $byWhat) 
    {
        return array('time'     =>  $time, 'by' =>  $byWhat);
    }
    
    function makeOneStep($currentPoint, $endPoint, $paths, $pathDone, $visitedPoint, $time)
    {
            static $allPath = array();
            
            foreach ($paths[$currentPoint] as $nextPoint => $value) {
                if ($nextPoint == $endPoint) {
                $result = array();
                $result['path'] = $pathDone;
                $result['path'][] = $endPoint;
                $result['time'] = $time + $paths[$currentPoint][$endPoint]['time'];;
                $allPath[] = $result;
                } elseif (!in_array($nextPoint, $visitedPoint)) {
                    /** если отправить массив visitedPoint и pathDone, то для последующих соседних точек (nextPoint)
                     *  они будут содержать информацию с предыдущей соседней точки, 
                     *  то есть массив для teh->vit, будет содержать инфорацию о пути для teh->sen  
                     */
                    $newPathDone = $pathDone;
                    $newPathDone[] = $nextPoint;
                    $newVisitedPoint = $visitedPoint;
                    $newVisitedPoint[] = $currentPoint;
                    $newTime = $time + $paths[$currentPoint][$nextPoint]['time'];
                    makeOneStep($nextPoint, $endPoint, $paths, $newPathDone, $newVisitedPoint, $newTime);
                }
            }

        /** Выбор оптимального пути по времени */
        
        $bestPath = array();
        $minTime = PHP_INT_MAX;
        
        foreach ($allPath as $path) {
            if ($path['time'] < $minTime) {
                $minTime = $path['time'];
                $bestPath = $path;
            }
        }
        return $bestPath;
    }
    
    function printTargetPath($startPoint, $endPoint, $targetPath, $paths, $pointNames, $transportName)
    {   
        $countTargetPoint = count($targetPath['path']);
        
        echo "Начальная точка: {$pointNames[$startPoint]}\n";
        for ($i = 0; $i < $countTargetPoint - 1; $i++) {
            /** Определение випа транспорта */
            $nmtransport = $transportName[$paths[$targetPath['path'][$i]][$targetPath['path'][$i + 1]]['by']];
            echo "Из нее {$nmtransport} до точки {$pointNames[$targetPath['path'][$i + 1]]} {$paths[$targetPath['path'][$i]][$targetPath['path'][$i + 1]]['time']} минут\n";
        }
        echo "В итоге ты попадаешь в точку " . $pointNames[$endPoint] . " за " . $targetPath['time'] . " минут. Приятной поездки!" ;
    }
    
    $visitedPoint = array();
    $pathDone = array($startPoint);
    $targetPath = array();
    $time = 0;

    $targetPath = makeOneStep($startPoint, $endPoint, $paths, $pathDone, $visitedPoint, $time);
    printTargetPath($startPoint, $endPoint, $targetPath, $paths, $pointNames, $transportName);
    
?>