<?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 initAlgorithm($paths, $pointNames, $transportName, $startPoint, $endPoint)
    {
        $paths[$startPoint]['label'] = 0;
        foreach ($paths as $point => &$pointValue) {
            if ($point != $startPoint) {
                $pointValue['label'] = PHP_INT_MAX;
            }
            $pointValue['visited'] = false;
        }

        doAlgorithmDeijkstra($paths, $pointNames, $transportName, $startPoint, $endPoint);
    }

    function printPaths($paths, $pointNames, $transportName, $targetPath, $startPoint, $endPoint)
    {
        echo "Начальная точка: " . $pointNames[$startPoint] . "\n";
        for ($i = 0; $i < count($targetPath) - 1; $i++) {
            $transport = $transportName[$paths[$targetPath[$i]][$targetPath[$i + 1]]['by']];
            echo "Из нее {$transport} до точки " . $pointNames[$targetPath[$i + 1]] . " " . $paths[$targetPath[$i]][$targetPath[$i+1]]['time'] ." минут\n";
        }
        echo "В итоге ты попадаешь в точку " . $pointNames[$endPoint] . " за " . $paths[$endPoint]['label'] . " минут. Приятной поездки!" ;
    }
    
    function searchPath($paths, $pointName, $transportName, $startPoint, $endPoint)
    {
        $currentPoint = $endPoint;
        $targetPath = array($currentPoint);
        
        while ($currentPoint != $startPoint) {
            foreach ($paths[$currentPoint] as $point => $pointValue) {
                if ($point == 'label' || $point == 'visited') {
                    continue;
                }
                if ($paths[$currentPoint]['label'] - $paths[$currentPoint][$point]['time'] == $paths[$point]['label']) {
                    $targetPath[] = $point;
                    $currentPoint = $point;
                    break;
                }
            }
        }

        $targetPath = array_reverse($targetPath);

        printPaths($paths, $pointName, $transportName, $targetPath, $startPoint, $endPoint);
    }

    function doAlgorithmDeijkstra($paths, $pointNames, $transportName, $startPoint, $endPoint)
    {
        $pointCount = count($paths);

        for ($i = 0; $i < $pointCount; $i++) {
            $minLabel = PHP_INT_MAX;
            $pointNameWork = NULL;

            foreach ($paths as $point => $pointValue) {
                if ($pointValue['label'] < $minLabel && (!$pointValue['visited'])) {
                    $minLabel = $pointValue['label'];
                    $pointNameWork = $point;
                }
            }

            $nextPoint = $paths[$pointNameWork];

            foreach ($nextPoint as $point => $pointValue) {
                if (!(array_key_exists($point, $pointNames))) {
                    continue;
                }
                $newLabel = $nextPoint['label'] + $paths[$pointNameWork][$point]['time'];
                if ($paths[$point]['label'] > $newLabel) {
                    $paths[$point]['label'] = $newLabel;
                }
            }

            $paths[$pointNameWork]['visited'] = true;
        }

        searchPath($paths, $pointNames, $transportName, $startPoint, $endPoint);
    }

    initAlgorithm($paths, $pointNames, $transportName, $startPoint, $endPoint);