<?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)
)
);
/* Чтобы не писать много раз array('time' => ..., 'by' => ...), используем функцию.
«canGet» переводится как «можно попасть» */
function canGet($time, $byWhat) {
return array('time' => $time, 'by' => $byWhat);
}
$numberOfPaths = array();
$numberOfPaths = array_keys($pointNames);
for ($i = 0; $i < count($numberOfPaths); $i++){
for ($j = 0; $j < count($numberOfPaths); $j++){
$communications[$i][$j] = 0;
}
}
//ПОСТРОЕНИЕ ТАБЛИЦЫ ДОРОГ
$connectedStops = array();
$trueConnectedStops = array();
foreach ($numberOfPaths as $key => $value) {
$connectedStops = array_keys($paths[$value]);
for ($i = 0; $i < count($connectedStops); $i++){
for ($j = 0; $j < count($numberOfPaths); $j++){
if ($numberOfPaths[$j] == $connectedStops[$i]){
$trueConnectedStops[$j] = $connectedStops[$i];
break;
}
}
}
foreach ($trueConnectedStops as $key2 => $value2) {
$communications[$key][$key2] = $paths[$value][$value2]['time'];
}
$trueConnectedStops = array();
}
//АЛГОРИТМ ПОИСКА САМОГО КОРОТКОГО МАРШРУТА
$maxTime = array();
$visitedStops = array();
for ($i = 0; $i < count($numberOfPaths); $i++){
$maxTime[$i] = 1000000;
$visitedStops[$i] = 1;
}
$maxTime[0] = 0;
do{
$minIndex = 1000000;
$minTime = 1000000;
for ($i = 0; $i < count($numberOfPaths); $i++){
if (($visitedStops[$i] == 1) && ($maxTime[$i] < $minTime)){
$minTime = $maxTime[$i];
$minIndex = $i;
}
}
if ($minIndex != 1000000){
for($i = 0; $i < count($numberOfPaths); $i++){
if ($communications[$minIndex][$i] > 0){
$temp = $minTime + $communications[$minIndex][$i];
if ($temp < $maxTime[$i]){
$maxTime[$i] = $temp;
}
}
}
$visitedStops[$minIndex] = 0;
}
} while ($minIndex < 1000000);
preferences:
54.57 ms | 402 KiB | 5 Q