<?php

error_reporting(-1);
/* http://d...content-available-to-author-only...2.net/ */
mb_internal_encoding("utf-8");

define('SUBWAY', 'sub');
define('FOOT', 'foot');
define('BUS', 'bus');

$transportName = array(
    SUBWAY => 'едешь на метро',
    FOOT => 'идешь пешком',
    BUS => 'едешь на автобусе'
);

$startPoint = 'kre'; // Петроградская
$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, SUBWAY),
        '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
    );
}

/*заполняем массив, который будет содержать метки для каждой из вершин а также
массив, в котором ведем учет уже проверенных вершин и массив, в который сохраняем отрезки пути */

$unChecked = array();
$marks     = array();
$roads     = array();

foreach ($paths as $point => $details) {
    static $i = 999;
    if ($point == $startPoint) {
        $marks[$point] = 0;
        $roads[$point] = "Из {$pointNames[$point]}";
    } else {
        $marks[$point] = $i++;
    }
    $unChecked[$point] = $marks[$point];
}

//echo "Starting from $startPoint... Destination : {$endPoint}\n";

while (!empty($unChecked)) {
    $unCheckedR = array_flip($unChecked);
    $min        = min(array_keys($unCheckedR));
    $curr       = $unCheckedR[$min];
  //  echo "Now curr is {$curr}\n";
    unset($unChecked[$curr]);
    $neighbours = $paths[$curr];
    
  //  echo "Neighbours are: ";
   // var_dump($neighbours);
  //  echo "\n";
    
    foreach ($neighbours as $station => $details) {
    //  echo "Starting cicle...\n";
    //  echo "neighbour is {$station}\n";
      //  echo "it's mark is {$marks[$station]}, curr's mark is {$marks[$curr]} (expecting 0).\n";
        if (($details["time"] + $marks[$curr]) <= $marks[$station]) {
        //  echo "TRUE!\n";
            $unChecked[$station] = $marks[$station] = $details["time"] + $marks[$curr];
         //  echo "time is {$details['time']}, {$station}\'s new mark is {$marks[$station]}.\n";
            $transport       = $details["by"];
            
            $roads[$station] = "{$roads[$curr]} {$transportName[$transport]} до {$pointNames[$station]} - {$details['time']} минут.\n";
            $roads[$station] .= ($station == $endPoint) ? "В итоге ты попадаешь в точку {$pointNames[$station]} за {$marks[$station]} минут.\n" : "Из неё";
        }
     // echo "now endPoint's mark is {$marks[$endPoint]}, endPoint's road is {$roads[$endPoint]}.\n";
    }
   // print_r($unChecked);
   //var_dump($roads[$endPoint]);
  // echo "deleting curr...\n";
}

echo $roads[$endPoint];