fork(1) 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('PATH_TO_ITSELF', -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. Возвращает пустой массив, если кратчайший путь не содержит промежуточных нодов.
  153. Иначе, возвращает массив промежуточных нодов.
  154. */
  155. function getPath($start, $end, $interimStep){
  156.     $shortestPath = array();
  157.     $temp = $end;
  158.     for ( ; $temp != $start; $temp = $interimStep[$start][$temp]) {
  159.         array_unshift($shortestPath, $temp);
  160.     }
  161.     return $shortestPath;
  162. }
  163.  
  164. /*
  165. Функция вывода пути.
  166. */
  167. function printPath($startPoint, $endPoint, $shortestPath, $paths, $pointNames, $pathCost){
  168.     if ($startPoint == $endPoint) {
  169.         echo "Ты собираешься попасть в точку, в которой уже находишься.(\"{$pointNames[$startPoint]}\")\n\n";
  170.         return;
  171.     }
  172.     echo "Начальная точка: \"{$pointNames[$startPoint]}\"\n";
  173.     $temp = $startPoint;
  174.     foreach ($shortestPath as $node) {
  175.         echo "Из нее {$paths[$temp][$node]['by']} до точки \"{$pointNames[$node]}\" {$pathCost[$temp][$node]} мин.\n";
  176.         $temp = $node;
  177.     }
  178.     echo "В итоге ты попадешь в точку \"{$pointNames[$endPoint]}\" за {$pathCost[$startPoint][$endPoint]} мин. Приятной поездки!\n\n";
  179. }
  180.  
  181. $numberOfNodes = count($pointNames);
  182.  
  183. /*
  184. Делаем квадратную матрицу путей размера $numberOfNodes, которая будет содержать время кратчайшего пути.
  185. Если путь не существует, то присваиваем ему значение бесконечности.
  186.  
  187. */
  188. $pathCost = array();
  189. for ($i = 0; $i < $numberOfNodes; $i++) {
  190.     for ($j = 0; $j < $numberOfNodes; $j++) {
  191.         if ($i == $j) {
  192.             $pathCost[$i][$j] = 0;
  193.         } elseif (!isset($paths[$i][$j]['time'])) {
  194.             $pathCost[$i][$j] = INF;
  195.         } else {
  196.             $pathCost[$i][$j] = $paths[$i][$j]['time'];
  197.         }
  198.     }
  199. }
  200.  
  201. //Массив, который будет содержать предпоследний шаг кратчайшего пути.
  202. $interimStep = array();
  203. for ($i = 0; $i < $numberOfNodes; $i++) {
  204.     $interimStep[$i] = array(); 
  205.     for ($j = 0; $j < $numberOfNodes; $j++) {
  206.         if ($i == $j) {
  207.             $interimStep[$i][$j] = PATH_TO_ITSELF;
  208.         } else {
  209.             $interimStep[$i][$j] = $i;
  210.         }
  211.     }
  212. }
  213.  
  214. //Алгоритм Флойда-Уоршелла.
  215. for ($k = 0; $k < $numberOfNodes; $k++) {
  216.     for ($i = 0; $i < $numberOfNodes; $i++) {
  217.         for ($j = 0; $j < $numberOfNodes; $j++) {
  218.             if (($pathCost[$i][$k] + $pathCost[$k][$j]) < $pathCost[$i][$j]) {
  219.                 $pathCost[$i][$j] = $pathCost[$i][$k] + $pathCost[$k][$j];
  220.                 $interimStep[$i][$j] = $interimStep[$k][$j];
  221.             }
  222.         }
  223.     }
  224. }
  225.  
  226. $startPoint = 0; // Петроградская
  227. $endPoint = 9; // Новая Голландия
  228. $shortestPath = getPath($startPoint, $endPoint, $interimStep);
  229. printPath($startPoint, $endPoint, $shortestPath, $paths, $pointNames, $pathCost);
  230.  
  231. //Сенная Площадь -> Новая Голландия
  232. $startPoint = 12;
  233. $endPoint = 9;
  234. $shortestPath = getPath($startPoint, $endPoint, $interimStep);
  235. printPath($startPoint, $endPoint, $shortestPath, $paths, $pointNames, $pathCost);
  236.  
  237. $startPoint = P_VIT;
  238. $endPoint = P_NOV;
  239. $shortestPath = getPath($startPoint, $endPoint, $interimStep);
  240. printPath($startPoint, $endPoint, $shortestPath, $paths, $pointNames, $pathCost);
  241.  
  242. $startPoint = P_LET;
  243. $endPoint = P_KRE;
  244. $shortestPath = getPath($startPoint, $endPoint, $interimStep);
  245. printPath($startPoint, $endPoint, $shortestPath, $paths, $pointNames, $pathCost);
  246.  
  247. $startPoint = P_NOV;
  248. $endPoint = P_NOV;
  249. $shortestPath = getPath($startPoint, $endPoint, $interimStep);
  250. printPath($startPoint, $endPoint, $shortestPath, $paths, $pointNames, $pathCost);
  251.  
  252. $startPoint = P_VAS;
  253. $endPoint = P_NOV;
  254. $shortestPath = getPath($startPoint, $endPoint, $interimStep);
  255. printPath($startPoint, $endPoint, $shortestPath, $paths, $pointNames, $pathCost);
Success #stdin #stdout 0.01s 20520KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Начальная точка: "ст. м. Петроградская"
Из нее едешь на метро до точки "ст. м. Горьковская" 3 мин.
Из нее едешь на метро до точки "Гостиный Двор" 6 мин.
Из нее едешь на метро до точки "Сенная Площадь" 3 мин.
Из нее идешь пешком до точки "Дом Раскольникова" 3 мин.
Из нее едешь на автобусе до точки "Новая Голландия" 7 мин.
В итоге ты попадешь в точку "Новая Голландия" за 22 мин. Приятной поездки!

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

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

Начальная точка: "Летний сад"
Из нее идешь пешком до точки "Гостиный Двор" 7 мин.
Из нее едешь на метро до точки "ст. м. Горьковская" 6 мин.
Из нее идешь пешком до точки "Петропавловская крепость" 5 мин.
В итоге ты попадешь в точку "Петропавловская крепость" за 18 мин. Приятной поездки!

Ты собираешься попасть в точку, в которой уже находишься.("Новая Голландия")

Начальная точка: "ст. м. Василеостровская"
Из нее идешь пешком до точки "Новая Голландия" 11 мин.
В итоге ты попадешь в точку "Новая Голландия" за 11 мин. Приятной поездки!
https://ideone.com/757ifw
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!