fork download
copy 
  1. <?php
  2.  
  3. error_reporting(-1);
  4. /* http://d...content-available-to-author-only...2.net/ */
  5.  mb_internal_encoding("utf-8");
  6.  
  7. define('SUBWAY', 'sub');
  8. define('FOOT', 'foot');
  9. define('BUS', 'bus');
  10.  
  11. $transportName = array(
  12. SUBWAY => 'едешь на метро',
  13. FOOT => 'идешь пешком',
  14. BUS => 'едешь на автобусе'
  15. );
  16.  
  17. $startPoint = 'pet'; // Петроградская
  18. $endPoint = 'nov'; // Новая Голландия
  19.  
  20. $pointNames = array(
  21. 'pet' => 'ст. м. Петроградская',
  22. 'chk' => 'ст. м. Чкаловская',
  23. 'gor' => 'ст. м. Горьковская',
  24. 'spo' => 'ст. м. Спортивная',
  25. 'vas' => 'ст. м. Василеостровская',
  26. 'kre' => 'Петропавловская крепость',
  27. 'let' => 'Летний сад',
  28. 'dvo' => 'Дворцовая площадь',
  29. 'isa' => 'Исакиевский собор',
  30. 'nov' => 'Новая Голландия',
  31. 'ras' => 'Дом Раскольникова',
  32. 'gos' => 'Гостиный Двор',
  33. 'sen' => 'Сенная Площадь',
  34. 'vla' => 'ст. м. Владимирская',
  35. 'vit' => 'Витебский вокзал',
  36. 'teh' => 'Технологический Институт'
  37. );
  38.  
  39. $paths = array(
  40.  
  41. 'pet' => array(
  42. 'chk' => canGet(10, BUS),
  43. 'gor' => canGet(3, SUBWAY)
  44. ),
  45.  
  46. 'chk' => array(
  47. 'pet' => canGet(10, BUS),
  48. 'spo' => canGet(3, SUBWAY)
  49. ),
  50.  
  51. 'gor' => array(
  52. 'pet' => canGet(3, BUS),
  53. 'kre' => canGet(5, FOOT),
  54. 'gos' => canGet(6, SUBWAY)
  55. ),
  56.  
  57. 'spo' => array(
  58. 'chk' => canGet(3, SUBWAY),
  59. 'vas' => canGet(10, BUS),
  60. 'sen' => canGet(7, SUBWAY)
  61. ),
  62.  
  63. 'vas' => array(
  64. 'spo' => canGet(10, BUS),
  65. 'gos' => canGet(7, SUBWAY),
  66. 'nov' => canGet(11, FOOT)
  67. ),
  68.  
  69. 'kre' => array(
  70. 'gor' => canGet(5, FOOT)
  71. ),
  72.  
  73. 'let' => array(
  74. 'dvo' => canGet(6, FOOT),
  75. 'gos' => canGet(7, FOOT)
  76. ),
  77.  
  78. 'dvo' => array(
  79. 'isa' => canGet(6, FOOT),
  80. 'gos' => canGet(6, FOOT),
  81. 'let' => canGet(6, FOOT)
  82. ),
  83.  
  84. 'isa' => array(
  85. 'dvo' => canGet(6, FOOT),
  86. 'nov' => canGet(5, FOOT)
  87. ),
  88.  
  89. 'nov' => array(
  90. 'vas' => canGet(11, FOOT),
  91. 'isa' => canGet(5, FOOT),
  92. 'ras' => canGet(7, BUS)
  93. ),
  94.  
  95. 'ras' => array(
  96. 'nov' => canGet(7, BUS),
  97. 'sen' => canGet(3, FOOT)
  98. ),
  99.  
  100. 'gos' => array(
  101. 'vas' => canGet(7, SUBWAY),
  102. 'sen' => canGet(3, SUBWAY),
  103. 'dvo' => canGet(6, FOOT),
  104. 'gor' => canGet(6, SUBWAY),
  105. 'let' => canGet(7, FOOT),
  106. 'vla' => canGet(7, FOOT)
  107. ),
  108.  
  109. 'sen' => array(
  110. 'ras' => canGet(3, FOOT),
  111. 'spo' => canGet(7, SUBWAY),
  112. 'gos' => canGet(3, SUBWAY),
  113. 'vla' => canGet(4, SUBWAY),
  114. 'vit' => canGet(2, SUBWAY),
  115. 'teh' => canGet(3, SUBWAY)
  116. ),
  117.  
  118. 'vla' => array(
  119. 'sen' => canGet(4, SUBWAY),
  120. 'gos' => canGet(7, FOOT),
  121. 'vit' => canGet(3, SUBWAY)
  122. ),
  123.  
  124. 'vit' => array(
  125. 'sen' => canGet(2, SUBWAY),
  126. 'teh' => canGet(2, SUBWAY),
  127. 'vla' => canGet(3, SUBWAY)
  128. ),
  129.  
  130. 'teh' => array(
  131. 'sen' => canGet(3, SUBWAY),
  132. 'vit' => canGet(2, SUBWAY)
  133. )
  134. );
  135.  
  136. /* Чтобы не писать много раз array('time' => ..., 'by' => ...), используем функцию.
  137.   «canGet» переводится как «можно попасть» */
  138. function canGet($time, $byWhat) {
  139. return array('time' => $time, 'by' => $byWhat);
  140. }
  141.  
  142. /*заполняем массив, который будет содержать метки для каждой из вершин а также
  143.  массив, в котором ведем учет уже проверенных вершин */
  144. $unChecked = array();
  145. $marks = array();
  146. $roads = array();
  147.  
  148. foreach ($paths as $point => $details) {
  149.  
  150.   if ($point == $startPoint) {
  151.     $marks[$point] = 0;
  152.     $roads[$point] = "Из {$pointNames[$point]}";
  153.   }
  154.   else {
  155.     $marks[$point] = 999;
  156.   }
  157.  
  158.   $unChecked[$point] = $marks[$point];
  159. }
  160.  
  161. while (!empty($unChecked)) {
  162.  
  163.     $min = min(array_keys((array_flip($unChecked))));
  164.     $curr = array_flip($unChecked)[$min];
  165.  
  166.     unset($unChecked[$curr]);
  167.  
  168.     $neighbours = $paths[$curr];
  169.  
  170.     foreach ($neighbours as $station => $details) {
  171.       if ( ($details["time"] + $marks[$curr]) < $marks[$station] ) {
  172.         $marks[$station] = $details["time"] + $marks[$curr];
  173.         $transport = $details["by"];
  174.  
  175.         //var_dump($transportName[$details["by"]]);
  176.  
  177.         $roads[$station] = "{$roads[$curr]} {$transportName[$transport]} до {$pointNames[$station]} - {$details["time"]} минут.\n";
  178.         $roads[$station] .= ($station == $endPoint) ? "В итоге ты попадаешь в точку {$pointNames[$station]} за {$marks[$station]} минут.\n" :
  179.                                                       "Из неё";
  180.       }
  181.     }
  182. }
  183.  
  184.  echo $roads[$endPoint];
  185.  
  186.  
Success #stdin #stdout #stderr 0.01s 20520KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
PHP Notice:  Undefined index: nov in /home/schbsP/prog.php on line 184
https://ideone.com/4DKBhk
language:
PHP (php 7.3.5)
created:
11 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!