fork(1) download
copy 
  1. <?php
  2.  
  3. error_reporting(-1);
  4.  
  5. define('SUBWAY', 'sub');
  6. define('FOOT', 'foot');
  7. define('BUS', 'bus');
  8.  
  9. $transportName = array(
  10.     SUBWAY => 'едешь на метро',
  11.     FOOT => 'идешь пешком',
  12.     BUS => 'едешь на автобусе'
  13. );
  14.  
  15. $startPoint = 'pet'; // Петроградская
  16. $endPoint = 'nov'; // Новая Голландия
  17.  
  18. $pointNames = array(
  19.     'pet' => 'ст. м. Петроградская',
  20.     'chk' => 'ст. м. Чкаловская',
  21.     'gor' => 'ст. м. Горьковская',
  22.     'spo' => 'ст. м. Спортивная',
  23.     'vas' => 'ст. м. Василеостровская',
  24.     'kre' => 'Петропавловская крепость',
  25.     'let' => 'Летний сад',
  26.     'dvo' => 'Дворцовая площадь',
  27.     'isa' => 'Исакиевский собор',
  28.     'nov' => 'Новая Голландия',
  29.     'ras' => 'Дом Раскольникова',
  30.     'gos' => 'Гостиный Двор',
  31.     'sen' => 'Сенная Площадь',
  32.     'vla' => 'ст. м. Владимирская',
  33.     'vit' => 'Витебский вокзал',
  34.     'teh' => 'Технолоческий Институт'
  35. );
  36.  
  37. $paths = array(
  38.     'pet' => array(
  39.         'chk' => canGet(10, BUS),
  40.         'gor' => canGet(3, SUBWAY)
  41.     ),
  42.  
  43.     'chk' => array(
  44.         'pet' => canGet(10, BUS),
  45.         'spo' => canGet(3, SUBWAY)
  46.     ),
  47.  
  48.     'gor' => array(
  49.         'pet' => canGet(3, BUS),
  50.         'kre' => canGet(5, FOOT),
  51.         'gos' => canGet(6, SUBWAY)
  52.     ),
  53.  
  54.     'spo' => array(
  55.         'chk' => canGet(3, SUBWAY),
  56.         'vas' => canGet(10, BUS),
  57.         'sen' => canGet(7, SUBWAY)
  58.     ),
  59.  
  60.     'vas' => array(
  61.         'spo' => canGet(10, BUS),
  62.         'gos' => canGet(7, SUBWAY),
  63.         'nov' => canGet(11, FOOT)
  64.     ),
  65.  
  66.     'kre' => array(
  67.         'gor' => canGet(5, FOOT)
  68.     ),
  69.  
  70.     'let' => array(
  71.         'dvo' => canGet(6, FOOT),
  72.         'gos' => canGet(7, FOOT)
  73.     ),
  74.  
  75.     'dvo' => array(
  76.         'isa' => canGet(6, FOOT),
  77.         'gos' => canGet(6, FOOT),
  78.         'let' => canGet(6, FOOT)
  79.     ),
  80.  
  81.     'isa' => array(
  82.         'dvo' => canGet(6, FOOT),
  83.         'nov' => canGet(5, FOOT)
  84.     ),
  85.  
  86.     'nov' => array(
  87.         'vas' => canGet(11, FOOT),
  88.         'isa' => canGet(5, FOOT),
  89.         'ras' => canGet(7, BUS)
  90.     ),
  91.  
  92.     'ras' => array(
  93.         'nov' => canGet(7, BUS),
  94.         'sen' => canGet(3, FOOT)
  95.     ),
  96.  
  97.     'gos' => array(
  98.         'vas' => canGet(7, SUBWAY),
  99.         'sen' => canGet(3, SUBWAY),
  100.         'dvo' => canGet(6, FOOT),
  101.         'gor' => canGet(6, SUBWAY),
  102.         'let' => canGet(7, FOOT),
  103.         'vla' => canGet(7, FOOT)
  104.     ),
  105.  
  106.     'sen' => array(
  107.         'ras' => canGet(3, FOOT),
  108.         'spo' => canGet(7, SUBWAY),
  109.         'gos' => canGet(3, SUBWAY),
  110.         'vla' => canGet(4, SUBWAY),
  111.         'vit' => canGet(2, SUBWAY),
  112.         'teh' => canGet(3, SUBWAY)
  113.     ),
  114.  
  115.     'vla' => array(
  116.         'sen' => canGet(4, SUBWAY),
  117.         'gos' => canGet(7, FOOT),
  118.         'vit' => canGet(3, SUBWAY)
  119.     ),
  120.  
  121.     'vit' => array(
  122.         'sen' => canGet(2, SUBWAY),
  123.         'teh' => canGet(2, SUBWAY),
  124.         'vla' => canGet(3, SUBWAY)
  125.     ),
  126.  
  127.     'teh' => array(
  128.         'sen' => canGet(3, SUBWAY),
  129.         'vit' => canGet(2, SUBWAY)
  130.     )
  131. );
  132.  
  133. /* Чтобы не писать много раз array('time' => ..., 'by' => ...), используем функцию.
  134.     «canGet» переводится как «можно попасть» */
  135. function canGet($time, $byWhat)
  136. {
  137.     return array('time' => $time, 'by' => $byWhat);
  138. }
  139.  
  140. # Возвращает ближайший узел
  141. function lowestWeightNode($weightOfActiveNodes)
  142. {
  143.     $lowestWeight = INF;
  144.     $lowestNode = null;
  145.     foreach ($weightOfActiveNodes as $node => $weightNode) {
  146.         if ($lowestWeight > $weightNode) {
  147.             $lowestWeight = $weightNode;
  148.             $lowestNode = $node;
  149.         }
  150.     }
  151.     return $lowestNode;
  152. }
  153.  
  154. function searchForAWay($startPoint, $endPoint, $paths, $transportName, $pointNames)
  155. {
  156.     $point = array_keys($paths);
  157.     $weightOfActiveNodes = array_fill_keys($point, INF); // Массив с весами узлов
  158.     $parentsNode = array_fill_keys($point, '');; // Массив с родительскикими узлами
  159.     $weightOfProcessedKnots = []; // Массив для обработаннхы узлов
  160.  
  161.     $weightOfActiveNodes[$startPoint] = 0; // Стартовой точке присваивается 0, для того, алгоритм поиска пути начался с неё
  162.     $node = lowestWeightNode($weightOfActiveNodes); // Находит узел с наименьшим весом
  163.  
  164.     while ($node != $endPoint) {
  165.         foreach ($paths[$node] as $neighbor => $timeAndBy) {
  166.             if (array_key_exists($neighbor, $weightOfActiveNodes)) { // 
  167.                 $weightNeighbor = $weightOfActiveNodes[$node] + $timeAndBy['time']; // весСоседа = рассматриваемый узел + путь до соседа
  168.                 if ($weightOfActiveNodes[$neighbor] > $weightNeighbor) { // Если текущий вес узла (рассматриваемого соседа) больше чем , новый найденный
  169.                     $parentsNode[$neighbor] = $node;
  170.                     $weightOfActiveNodes[$neighbor] = $weightNeighbor;
  171.                 }
  172.             }
  173.         }
  174.         $weightOfProcessedKnots[$node] = $weightOfActiveNodes[$node];
  175.         unset($weightOfActiveNodes[$node]);
  176.         $node = lowestWeightNode($weightOfActiveNodes);
  177.     }
  178.  
  179.     $commonPath = []; // Кратчайший, требуемый путь
  180.     $finishPoint = $endPoint;
  181.     while ($finishPoint != $startPoint) {
  182.         $commonPath[$finishPoint] = $parentsNode[$finishPoint];
  183.         $finishPoint = $parentsNode[$finishPoint];
  184.     }
  185.     $commonPath = array_reverse($commonPath);
  186.  
  187.     #Вывод пути
  188.     $totalTime = 0;
  189.     foreach ($commonPath as $startPoint => $FinishPoint) {
  190.         $wayOfMovement = $transportName[$paths[$startPoint][$FinishPoint]['by']];
  191.         echo "Из неё {$wayOfMovement} до точки {$pointNames[$startPoint]} {$paths[$startPoint][$FinishPoint]['time']} мин." . PHP_EOL;
  192.         $totalTime += $paths[$startPoint][$FinishPoint]['time'];
  193.     }
  194.     echo "В итоге ты попадешь в точку {$pointNames[$endPoint]} за {$totalTime} минут";
  195. }
  196.  
  197. searchForAWay($startPoint, $endPoint, $paths, $transportName, $pointNames);
Success #stdin #stdout 0.02s 24592KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Из неё едешь на автобусе до точки ст. м. Горьковская 3 мин.
Из неё едешь на метро до точки Гостиный Двор 6 мин.
Из неё едешь на метро до точки Сенная Площадь 3 мин.
Из неё идешь пешком до точки Дом Раскольникова 3 мин.
Из неё едешь на автобусе до точки Новая Голландия 7 мин.
В итоге ты попадешь в точку Новая Голландия за 22 минут
https://ideone.com/q1Uk29
language:
PHP (php 7.3.5)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!