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