fork download
copy 
  1. <?php
  2.  
  3. error_reporting(-1);
  4. /* http://d...content-available-to-author-only...2.net/ */
  5.  
  6. define('SUBWAY', "едешь на метро");
  7. define('FOOT', "идешь пешком");
  8. define('BUS', "едешь на автобусе");
  9.  
  10. define('P_PET', 0);
  11. define('P_CHK', 1);
  12. define('P_GOR', 2);
  13. define('P_SPO', 3);
  14. define('P_VAS', 4);
  15. define('P_KRE', 5);
  16. define('P_LET', 6);
  17. define('P_DVO', 7);
  18. define('P_ISA', 8);
  19. define('P_NOV', 9);
  20. define('P_RAS', 10);
  21. define('P_GOS', 11);
  22. define('P_SEN', 12);
  23. define('P_VLA', 13);
  24. define('P_VIT', 14);
  25. define('P_TEH', 15);
  26.  
  27. define('UNKNOWN', -1);
  28.  
  29. /* Чтобы не писать много раз array('time' => ..., 'by' => ...), используем функцию. 
  30.     «canGet» переводится как «можно попасть» */
  31. function canGet($time, $byWhat) {
  32.     return array('time'     =>  $time, 'by' =>  $byWhat);
  33. }
  34.  
  35. $pointNames = array(
  36.     P_PET   =>  'ст. м. Петроградская',
  37.     P_CHK   =>  'ст. м. Чкаловская',
  38.     P_GOR   =>  'ст. м. Горьковская',
  39.     P_SPO   =>  'ст. м. Спортивная',
  40.     P_VAS   =>  'ст. м. Василеостровская',
  41.     P_KRE   =>  'Петропавловская крепость',
  42.     P_LET   =>  'Летний сад',
  43.     P_DVO   =>  'Дворцовая площадь',
  44.     P_ISA   =>  'Исакиевский собор',
  45.     P_NOV   =>  'Новая Голландия',
  46.     P_RAS   =>  'Дом Раскольникова',
  47.     P_GOS   =>  'Гостиный Двор',
  48.     P_SEN   =>  'Сенная Площадь',
  49.     P_VLA   =>  'ст. м. Владимирская',
  50.     P_VIT   =>  'Витебский вокзал',
  51.     P_TEH   =>  'Технологический Институт'
  52. );
  53.  
  54. $paths = array(
  55.     P_PET   =>  array(
  56.         P_CHK   =>  canGet(10, BUS),
  57.         P_GOR   =>  canGet(3, SUBWAY)
  58.     ),
  59.  
  60.     P_CHK   =>  array(
  61.         P_PET   =>  canGet(10, BUS),
  62.         P_SPO   =>  canGet(3, SUBWAY)
  63.     ),
  64.  
  65.     P_GOR   =>  array(
  66.         P_PET   =>  canGet(3, BUS),
  67.         P_KRE   =>  canGet(5, FOOT),
  68.         P_GOS   =>  canGet(6, SUBWAY)
  69.     ),
  70.  
  71.     P_SPO   =>  array(
  72.         P_CHK   =>  canGet(3, SUBWAY),
  73.         P_VAS   =>  canGet(10, BUS),
  74.         P_SEN   =>  canGet(7, SUBWAY)
  75.     ),
  76.  
  77.     P_VAS   =>  array(
  78.         P_SPO   =>  canGet(10, BUS),
  79.         P_GOS   =>  canGet(7, SUBWAY),
  80.         P_NOV   =>  canGet(11, FOOT)
  81.     ),
  82.  
  83.     P_KRE   =>  array(
  84.         P_GOR   =>  canGet(5, FOOT)
  85.     ),
  86.  
  87.     P_LET   =>  array(
  88.         P_DVO   =>  canGet(6, FOOT),
  89.         P_GOS   =>  canGet(7, FOOT)
  90.     ),
  91.  
  92.     P_DVO   =>  array(
  93.         P_ISA   =>  canGet(6, FOOT),
  94.         P_GOS   =>  canGet(6, FOOT),
  95.         P_LET   =>  canGet(6, FOOT)
  96.     ),
  97.  
  98.     P_ISA   =>  array(
  99.         P_DVO   =>  canGet(6, FOOT),
  100.         P_NOV   =>  canGet(5, FOOT)
  101.     ),
  102.  
  103.     P_NOV   =>  array(
  104.         P_VAS   =>  canGet(11, FOOT),
  105.         P_ISA   =>  canGet(5, FOOT),
  106.         P_RAS   =>  canGet(7, BUS)
  107.     ),
  108.  
  109.     P_RAS   =>  array(
  110.         P_NOV   =>  canGet(7, BUS),
  111.         P_SEN   =>  canGet(3, FOOT)
  112.     ),
  113.  
  114.     P_GOS   =>  array(
  115.         P_VAS   =>  canGet(7, SUBWAY),
  116.         P_SEN   =>  canGet(3, SUBWAY),
  117.         P_DVO   =>  canGet(6, FOOT),
  118.         P_GOR   =>  canGet(6, SUBWAY),
  119.         P_LET   =>  canGet(7, FOOT),
  120.         P_VLA   =>  canGet(7, FOOT)        
  121.     ),
  122.  
  123.     P_SEN   =>  array(
  124.         P_RAS   =>  canGet(3, FOOT),
  125.         P_SPO   =>  canGet(7, SUBWAY),
  126.         P_GOS   =>  canGet(3, SUBWAY),
  127.         P_VLA   =>  canGet(4, SUBWAY),
  128.         P_VIT   =>  canGet(2, SUBWAY),
  129.         P_TEH   =>  canGet(3, SUBWAY)
  130.     ),
  131.  
  132.     P_VLA   =>  array(
  133.         P_SEN   =>  canGet(4, SUBWAY),
  134.         P_GOS   =>  canGet(7, FOOT),
  135.         P_VIT   =>  canGet(3, SUBWAY)
  136.     ),
  137.  
  138.     P_VIT   =>  array(
  139.         P_SEN   =>  canGet(2, SUBWAY),
  140.         P_TEH   =>  canGet(2, SUBWAY),
  141.         P_VLA   =>  canGet(3, SUBWAY)
  142.     ),
  143.  
  144.     P_TEH   =>  array(
  145.         P_SEN   =>  canGet(3, SUBWAY),
  146.         P_VIT   =>  canGet(2, SUBWAY)        
  147.     )
  148. );
  149.  
  150.  
  151. /*Функция построения кратчайшего пути.
  152. Возвращает NULL, если кратчайший путь не содержит промежуточных нодов.
  153. Иначе, возвращает массив промежуточных нодов.
  154. */
  155. function getPath($start, $end, $interimStep){
  156.     if ($interimStep[$start][$end] == INF) {
  157.         return NULL;
  158.     }
  159.     $shortestPath = array();
  160.     $temp = $end;
  161.     while ($temp != UNKNOWN) {
  162.         $temp = $interimStep[$start][$temp];
  163.         array_unshift($shortestPath, $temp);
  164.     }
  165.     unset($shortestPath[0]);
  166.     return $shortestPath;
  167. }
  168.  
  169. /*
  170. Функция вывода пути.
  171. */
  172. function printPath($startPoint, $endPoint, $shortestPath, $paths, $pointNames){
  173.     echo "Начальная точка: \"{$pointNames[$startPoint]}\"\n";
  174.     $temp = $startPoint;
  175.     if ($shortestPath != NULL) {
  176.         $temp = $startPoint;
  177.         foreach ($shortestPath as $node) {
  178.             echo "Из нее {$paths[$temp][$node]['by']} до точки \"{$pointNames[$node]}\" {$paths[$temp][$node]['time']} мин.\n";
  179.             $temp = $node;
  180.         }
  181.     }
  182.     echo "Из нее {$paths[$temp][$endPoint]['by']} до точки \"{$pointNames[$endPoint]}\" {$paths[$temp][$endPoint]['time']} мин.\n";
  183.     echo "В итоге ты попадешь в точку \"{$pointNames[$endPoint]}\" за {$paths[$startPoint][$endPoint]['time']} мин. Приятной поездки!\n\n";
  184. }
  185.  
  186. $numberOfNodes = count($pointNames);
  187.  
  188. /*Делаем квадратную матрицу путей размера $numberOfNodes, которая будет содержать время кратчайшего пути.
  189. Если путь не существует, то присваиваем ему значение бесконечности.
  190. */
  191. foreach ($paths as $i => $array) {
  192.     for ($j = 0; $j < $numberOfNodes; $j++) {
  193.         if (isset($paths[$i][$j]['time']) == NULL) {
  194.             $paths[$i][$j]['time'] = INF;
  195.         }
  196.     }
  197. }
  198.  
  199. //Массив, который будет содержать предпоследний шаг кратчайшего пути.
  200. $interimStep = array();
  201. for ($i = 0; $i < $numberOfNodes; $i++) {
  202.     $interimStep[$i] = array_fill(0, $numberOfNodes, UNKNOWN);
  203. }
  204.  
  205. //Алгоритм Флойда-Уоршелла.
  206. for ($k = 0; $k < $numberOfNodes; $k++) {
  207.     for ($i = 0; $i < $numberOfNodes; $i++) {
  208.         for ($j = 0; $j < $numberOfNodes; $j++) {
  209.             if (($paths[$i][$k]['time'] + $paths[$k][$j]['time']) < $paths[$i][$j]['time']) {
  210.                 $paths[$i][$j]['time'] = $paths[$i][$k]['time'] + $paths[$k][$j]['time'];
  211.                 $interimStep[$i][$j] = $k;
  212.             }
  213.         }
  214.     }
  215. }
  216.  
  217. //Тут вылетает предпоследняя нода (дом Раскольникова), но время всего пути выводится корректно.
  218. $startPoint = 0; // Петроградская
  219. $endPoint = 9; // Новая Голландия
  220. $shortestPath = getPath($startPoint, $endPoint, $interimStep);
  221. printPath($startPoint, $endPoint, $shortestPath, $paths, $pointNames);
  222.  
  223. //Сенная Площадь -> Новая Голландия
  224. //Тут все выводится корректно.
  225. $startPoint = 12;
  226. $endPoint = 9;
  227. $shortestPath = getPath($startPoint, $endPoint, $interimStep);
  228. printPath($startPoint, $endPoint, $shortestPath, $paths, $pointNames);
  229.  
  230. $startPoint = P_VIT;
  231. $endPoint = P_NOV;
  232. $shortestPath = getPath($startPoint, $endPoint, $interimStep);
  233. printPath($startPoint, $endPoint, $shortestPath, $paths, $pointNames);
  234.  
  235. $startPoint = P_TEH;
  236. $endPoint = P_NOV;
  237. $shortestPath = getPath($startPoint, $endPoint, $interimStep);
  238. printPath($startPoint, $endPoint, $shortestPath, $paths, $pointNames);
  239.  
Success #stdin #stdout #stderr 0.01s 20520KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Начальная точка: "ст. м. Петроградская"
Из нее едешь на метро до точки "ст. м. Горьковская" 3 мин.
Из нее едешь на метро до точки "Гостиный Двор" 6 мин.
Из нее едешь на метро до точки "Сенная Площадь" 3 мин.
Из нее  до точки "Новая Голландия" 10 мин.
В итоге ты попадешь в точку "Новая Голландия" за 22 мин. Приятной поездки!

Начальная точка: "Сенная Площадь"
Из нее идешь пешком до точки "Дом Раскольникова" 3 мин.
Из нее едешь на автобусе до точки "Новая Голландия" 7 мин.
В итоге ты попадешь в точку "Новая Голландия" за 10 мин. Приятной поездки!

Начальная точка: "Витебский вокзал"
Из нее едешь на метро до точки "Сенная Площадь" 2 мин.
Из нее  до точки "Новая Голландия" 10 мин.
В итоге ты попадешь в точку "Новая Голландия" за 12 мин. Приятной поездки!

Начальная точка: "Технологический Институт"
Из нее едешь на метро до точки "Сенная Площадь" 3 мин.
Из нее  до точки "Новая Голландия" 10 мин.
В итоге ты попадешь в точку "Новая Голландия" за 13 мин. Приятной поездки!
stderr
copy 
PHP Notice:  Undefined index: by in /home/YtmJVF/prog.php on line 182
PHP Notice:  Undefined index: by in /home/YtmJVF/prog.php on line 182
PHP Notice:  Undefined index: by in /home/YtmJVF/prog.php on line 182
https://ideone.com/sFOrpI
language:
PHP (php 7.3.5)
created:
10 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!