fork download
copy 
  1. <?php
  2.  
  3.  error_reporting(-1);
  4.  /* http://d...content-available-to-author-only...2.net/ */
  5.  
  6.  define('SUBWAY', 'sub');
  7.  define('FOOT', 'foot');
  8.  define('BUS', 'bus');
  9.  
  10.  $transportName = array(
  11.      SUBWAY  =>  'едешь на метро',
  12.      FOOT    =>  'идешь пешком',
  13.      BUS     =>  'едешь на автобусе'
  14.  );
  15.  
  16.  $startPoint = 'pet'; // Петроградская
  17.  $endPoint = 'vit'; // Новая Голландия
  18.  
  19.  $pointNames = array(
  20.      'pet'   =>  'ст. м. Петроградская',
  21.      'chk'   =>  'ст. м. Чкаловская',
  22.      'gor'   =>  'ст. м. Горьковская',
  23.      'spo'   =>  'ст. м. Спортивная',
  24.      'vas'   =>  'ст. м. Василеостровская',
  25.      'kre'   =>  'Петропавловская крепость',
  26.      'let'   =>  'Летний сад',
  27.      'dvo'   =>  'Дворцовая площадь',
  28.      'isa'   =>  'Исакиевский собор',
  29.      'nov'   =>  'Новая Голландия',
  30.      'ras'   =>  'Дом Раскольникова',
  31.      'gos'   =>  'Гостиный Двор',
  32.      'sen'   =>  'Сенная Площадь',
  33.      'vla'   =>  'ст. м. Владимирская',
  34.      'vit'   =>  'Витебский вокзал',
  35.      'teh'   =>  'Технологический Институт'
  36.  );
  37.  
  38.  $paths = array(
  39.      'pet'   =>  array(
  40.          'chk'   =>  canGet(10, BUS),
  41.          'gor'   =>  canGet(3, SUBWAY)
  42.      ),
  43.  
  44.      'chk'   =>  array(
  45.          'pet'   =>  canGet(10, BUS),
  46.          'spo'   =>  canGet(3, SUBWAY)
  47.      ),
  48.  
  49.      'gor'   =>  array(
  50.          'pet'   =>  canGet(3, BUS),
  51.          'kre'   =>  canGet(5, FOOT),
  52.          'gos'   =>  canGet(6, SUBWAY)
  53.      ),
  54.  
  55.      'spo'   =>  array(
  56.          'chk'   =>  canGet(3, SUBWAY),
  57.          'vas'   =>  canGet(10, BUS),
  58.          'sen'   =>  canGet(7, SUBWAY)
  59.      ),
  60.  
  61.      'vas'   =>  array(
  62.          'spo'   =>  canGet(10, BUS),
  63.          'gos'   =>  canGet(7, SUBWAY),
  64.          'nov'   =>  canGet(11, FOOT)
  65.      ),
  66.  
  67.      'kre'   =>  array(
  68.          'gor'   =>  canGet(5, FOOT)
  69.      ), 
  70.  
  71.      'let'   =>  array(
  72.          'dvo'   =>  canGet(6, FOOT),
  73.          'gos'   =>  canGet(7, FOOT)
  74.      ),
  75.  
  76.      'dvo'   =>  array(
  77.          'isa'   =>  canGet(6, FOOT),
  78.          'gos'   =>  canGet(6, FOOT),
  79.          'let'   =>  canGet(6, FOOT)
  80.      ),
  81.  
  82.      'isa'   =>  array(
  83.          'dvo'   =>  canGet(6, FOOT),
  84.          'nov'   =>  canGet(5, FOOT)
  85.      ),
  86.  
  87.      'nov'   =>  array(
  88.          'vas'   =>  canGet(11, FOOT),
  89.          'isa'   =>  canGet(5, FOOT),
  90.          'ras'   =>  canGet(7, BUS)
  91.      ),
  92.  
  93.      'ras'   =>  array(
  94.          'nov'   =>  canGet(7, BUS),
  95.          'sen'   =>  canGet(3, FOOT)
  96.      ),
  97.  
  98.      'gos'   =>  array(
  99.          'vas'   =>  canGet(7, SUBWAY),
  100.          'sen'   =>  canGet(3, SUBWAY),
  101.          'dvo'   =>  canGet(6, FOOT),
  102.          'gor'   =>  canGet(6, SUBWAY),
  103.          'let'   =>  canGet(7, FOOT),
  104.          'vla'   =>  canGet(7, FOOT)        
  105.      ),
  106.  
  107.      'sen'   =>  array(
  108.          'ras'   =>  canGet(3, FOOT),
  109.          'spo'   =>  canGet(7, SUBWAY),
  110.          'gos'   =>  canGet(3, SUBWAY),
  111.          'vla'   =>  canGet(4, SUBWAY),
  112.          'vit'   =>  canGet(2, SUBWAY),
  113.          'teh'   =>  canGet(3, SUBWAY)
  114.      ),
  115.  
  116.      'vla'   =>  array(
  117.          'sen'   =>  canGet(4, SUBWAY),
  118.          'gos'   =>  canGet(7, FOOT),
  119.          'vit'   =>  canGet(3, SUBWAY)
  120.      ),
  121.  
  122.      'vit'   =>  array(
  123.          'sen'   =>  canGet(2, SUBWAY),
  124.          'teh'   =>  canGet(2, SUBWAY),
  125.          'vla'   =>  canGet(3, SUBWAY)
  126.      ),
  127.  
  128.      'teh'   =>  array(
  129.          'sen'   =>  canGet(3, SUBWAY),
  130.          'vit'   =>  canGet(2, SUBWAY)        
  131.      )
  132.  );
  133.  
  134.  /* Чтобы не писать много раз array('time' => ..., 'by' => ...), используем функцию. 
  135.      «canGet» переводится как «можно попасть» */
  136.  function canGet($time, $byWhat) {
  137.      return array('time'     =>  $time, 'by' =>  $byWhat);
  138.  }
  139.  
  140. // Текущий путь
  141. $currentPath        = []; 
  142. $currentPath[]      = $startPoint;
  143. // Время, затраченное на текущий путь
  144. $time               = 0;
  145.  
  146. //Самый быстрый путь 
  147. $winPath            = [];
  148. // Его время (по умолчанию рандом большое число)
  149. $winTime            = 999999;
  150.  
  151.  
  152. // Основная функция расчета, которая проходит по всему усл. графу
  153. function oneStep ($currentPath, $startPoint, $endPoint, $paths, $time){
  154.  
  155.     // Обращаемся к глобальным переменным
  156.     global $winPath;
  157.     global $winTime;
  158.     // Счетчик, который позволяет понять, к какому элементу мы обращаемся (для проверки, не является ли элемент последним)
  159.     $count = 0;
  160.  
  161.     // Перебор всех возможных путей
  162.     foreach ($paths[$startPoint] as $changeStation => $value) {
  163.         $count++;
  164.  
  165.         // Если мы уже были на станции, на которую собираемся пойти
  166.         if ( in_array ( $changeStation, $currentPath) ) {
  167.             // Если эта станция не последняя в текущем списке
  168.             if ( ! ($count == count ($paths[$startPoint])) ){
  169.                 continue;
  170.             }
  171.             else {
  172.                 return;
  173.             } 
  174.         }
  175.  
  176.         // Обновляем текущий список и время
  177.         $currentPath    []= $changeStation;    
  178.         $time           += $value['time'];
  179.  
  180.         // Если нашли выигрышный путь
  181.         if ( $changeStation == $endPoint ){
  182.             // Время выигрышного путя меньше, чем выигрышнуй путь по умолч.
  183.             if ($winTime > $time) {
  184.                 $winPath    = $currentPath;
  185.                 $winTime    = $time;
  186.             }
  187.  
  188.             // Сбрасываем последнюю переменную, так как мы не "пойдем" на эту станцию
  189.             $bif    = array_pop ($currentPath);
  190.  
  191.             // Если  это не последний элемент списка
  192.             if ( ! ($count == count ($paths[$startPoint])) ){
  193.                 continue;
  194.             }
  195.             else {
  196.                 return;
  197.             } 
  198.         }
  199.  
  200.         oneStep ($currentPath, $changeStation, $endPoint, $paths, $time); 
  201.  
  202.         // После вовзрата из "стека", необходимо отбросить последнюю переменную, так как она записана в текущий путь ($currentPath)
  203.         $bif    = array_pop ($currentPath);
  204.         // Аналогичным образом сбрасываем время
  205.         $time   -= $value['time'];
  206.     }
  207. }
  208.  
  209. oneStep ($currentPath, $startPoint, $endPoint, $paths, $time);
  210.  
  211.  
  212. // Выводим информацию
  213.  
  214. // Вспомогательная переменная, которая запоминает предыдущую станцию
  215. $beforeStation;
  216.  
  217. echo "Чтобы добраться с {$pointNames[$startPoint]} до {$pointNames[$endPoint]} за {$winTime} минут, вам нужно: <br>";
  218. foreach ($winPath as $count => $value) {
  219.  
  220.     if ($count == 0) {
  221.         $beforeStation = $value;
  222.         continue;
  223.     }
  224.  
  225.     echo "От {$pointNames[$beforeStation]} " . 
  226.         $transportName[$paths[$beforeStation][$value]['by']] .
  227.         " до " . $pointNames[$beforeStation] . " за " .
  228.         $paths[$beforeStation][$value]['time'] . " минуты.<br>";
  229.  
  230.     $beforeStation = $value;
  231. }
  232.  
  233.  
  234. ?>
Success #stdin #stdout 0.02s 24724KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Чтобы добраться с ст. м. Петроградская до Витебский вокзал за 14 минут, вам нужно: <br>От ст. м. Петроградская едешь на метро до ст. м. Петроградская за 3 минуты.<br>От ст. м. Горьковская едешь на метро до ст. м. Горьковская за 6 минуты.<br>От Гостиный Двор едешь на метро до Гостиный Двор за 3 минуты.<br>От Сенная Площадь едешь на метро до Сенная Площадь за 2 минуты.<br>
https://ideone.com/y1YVYt
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!