fork(2) download
  1. <?php
  2.  
  3.  
  4. define('SUBWAY', 'sub');
  5. define('FOOT', 'foot');
  6. define('BUS', 'bus');
  7.  
  8. $transportName = array(
  9. SUBWAY => 'едешь на метро',
  10. FOOT => 'идешь пешком',
  11. BUS => 'едешь на автобусе'
  12. );
  13.  
  14. $startPoint = 'pet'; // Петроградская
  15. $endPoint = 'nov'; // Новая Голландия
  16.  
  17. $pointNames = array(
  18. 'pet' => 'ст. м. Петроградская',
  19. 'chk' => 'ст. м. Чкаловская',
  20. 'gor' => 'ст. м. Горьковская',
  21. 'spo' => 'ст. м. Спортивная',
  22. 'vas' => 'ст. м. Василеостровская',
  23. 'kre' => 'Петропавловская крепость',
  24. 'let' => 'Летний сад',
  25. 'dvo' => 'Дворцовая площадь',
  26. 'isa' => 'Исакиевский собор',
  27. 'nov' => 'Новая Голландия',
  28. 'ras' => 'Дом Раскольникова',
  29. 'gos' => 'Гостиный Двор',
  30. 'sen' => 'Сенная Площадь',
  31. 'vla' => 'ст. м. Владимирская',
  32. 'vit' => 'Витебский вокзал',
  33. 'teh' => 'Технологический Институт'
  34. );
  35.  
  36. $paths = array(
  37. 'pet' => array(
  38. 'chk' => canGet(10, BUS),
  39. 'gor' => canGet(3, SUBWAY)
  40. ),
  41.  
  42. 'chk' => array(
  43. 'pet' => canGet(10, BUS),
  44. 'spo' => canGet(3, SUBWAY)
  45. ),
  46.  
  47. 'gor' => array(
  48. 'pet' => canGet(3, BUS),
  49. 'kre' => canGet(5, FOOT),
  50. 'gos' => canGet(6, SUBWAY)
  51. ),
  52.  
  53. 'spo' => array(
  54. 'chk' => canGet(3, SUBWAY),
  55. 'vas' => canGet(10, BUS),
  56. 'sen' => canGet(7, SUBWAY)
  57. ),
  58.  
  59. 'vas' => array(
  60. 'spo' => canGet(10, BUS),
  61. 'gos' => canGet(7, SUBWAY),
  62. 'nov' => canGet(11, FOOT)
  63. ),
  64.  
  65. 'kre' => array(
  66. 'gor' => canGet(5, FOOT)
  67. ),
  68.  
  69. 'let' => array(
  70. 'dvo' => canGet(6, FOOT),
  71. 'gos' => canGet(7, FOOT)
  72. ),
  73.  
  74. 'dvo' => array(
  75. 'isa' => canGet(6, FOOT),
  76. 'gos' => canGet(6, FOOT),
  77. 'let' => canGet(6, FOOT)
  78. ),
  79.  
  80. 'isa' => array(
  81. 'dvo' => canGet(6, FOOT),
  82. 'nov' => canGet(5, FOOT)
  83. ),
  84.  
  85. 'nov' => array(
  86. 'vas' => canGet(11, FOOT),
  87. 'isa' => canGet(5, FOOT),
  88. 'ras' => canGet(7, BUS)
  89. ),
  90.  
  91. 'ras' => array(
  92. 'nov' => canGet(7, BUS),
  93. 'sen' => canGet(3, FOOT)
  94. ),
  95.  
  96. 'gos' => array(
  97. 'vas' => canGet(7, SUBWAY),
  98. 'sen' => canGet(3, SUBWAY),
  99. 'dvo' => canGet(6, FOOT),
  100. 'gor' => canGet(6, SUBWAY),
  101. 'let' => canGet(7, FOOT),
  102. 'vla' => canGet(7, FOOT)
  103. ),
  104.  
  105. 'sen' => array(
  106. 'ras' => canGet(3, FOOT),
  107. 'spo' => canGet(7, SUBWAY),
  108. 'gos' => canGet(3, SUBWAY),
  109. 'vla' => canGet(4, SUBWAY),
  110. 'vit' => canGet(2, SUBWAY),
  111. 'teh' => canGet(3, SUBWAY)
  112. ),
  113.  
  114. 'vla' => array(
  115. 'sen' => canGet(4, SUBWAY),
  116. 'gos' => canGet(7, FOOT),
  117. 'vit' => canGet(3, SUBWAY)
  118. ),
  119.  
  120. 'vit' => array(
  121. 'sen' => canGet(2, SUBWAY),
  122. 'teh' => canGet(2, SUBWAY),
  123. 'vla' => canGet(3, SUBWAY)
  124. ),
  125.  
  126. 'teh' => array(
  127. 'sen' => canGet(3, SUBWAY),
  128. 'vit' => canGet(2, SUBWAY)
  129. ),
  130. 'isa' => array(
  131. 'dvo' => canGet(6, FOOT),
  132. 'nov' => canGet(5, FOOT)
  133. ),
  134.  
  135. );
  136.  
  137. /* Чтобы не писать много раз array('time' => ..., 'by' => ...), используем функцию.
  138.   «canGet» переводится как «можно попасть» */
  139. function canGet($time, $byWhat)
  140. {
  141. return array('time' => $time, 'by' => $byWhat);
  142. }
  143.  
  144. function makeOneMoreStep($paths, $pathDone, $time, $point, $target)
  145. {
  146. static $possibleWays, $possibleTimes;
  147. if (array_key_exists($target, $paths[$point])) {
  148. $time += $paths[$point][$target]['time'];
  149. $pathDone[] = $target;
  150.  
  151. $possibleWays[] = $pathDone;
  152. $possibleTimes[] = $time;
  153. return;
  154. } else {
  155. foreach ($paths[$point] as $subTarget => $timeAndBy) {
  156. if (!in_array($subTarget, $pathDone)) {
  157. makeOneMoreStep($paths, array_merge($pathDone, [$subTarget]), $time + $paths[$point][$subTarget]['time'], $subTarget, $target);
  158. }
  159. }
  160. }
  161. return ['ways' => $possibleWays, 'travel time' => $possibleTimes];
  162. }
  163.  
  164. $point = 'pet'; // Старт
  165. $target = 'nov'; // Финиш
  166. $pathDone = [$point];
  167. $time = 0;
  168.  
  169. $target = 'nov';
  170.  
  171. $waysAndTime = makeOneMoreStep($paths, $pathDone, $time, $point, $target);
  172. print_r($waysAndTime);
  173. $bestTime = min($waysAndTime['travel time']); // Лучшее время
  174. $pathNumber = array_keys($waysAndTime['travel time'], $bestTime)[0]; // Ключ лучшего варианта перемещния
  175. $bestPath = $waysAndTime['ways'][$pathNumber]; // лучший вариант перемещения
  176. print_r($bestPath);
  177.  
  178. # Вывод пути
  179. echo "Начальная точка: $pointNames[$startPoint]".PHP_EOL;
  180. for($i = 0;$i<count($bestPath)-1;$i++){
  181. $a = $bestPath[$i];
  182. $b = $bestPath[$i+1];
  183. echo "Из нее {$transportName[$paths[$a][$b]['by']]} до точки {$pointNames[$bestPath[$i+1]]} {$paths[$a][$b]['time']} мин".PHP_EOL;
  184. }
  185. echo "В итоге ты попадешь в точку {$pointNames[$b]} за {$bestTime} минут ";
Success #stdin #stdout 0.02s 24356KB
stdin
Standard input is empty
stdout
Array
(
    [ways] => Array
        (
            [0] => Array
                (
                    [0] => pet
                    [1] => chk
                    [2] => spo
                    [3] => vas
                    [4] => nov
                )

            [1] => Array
                (
                    [0] => pet
                    [1] => chk
                    [2] => spo
                    [3] => sen
                    [4] => ras
                    [5] => nov
                )

            [2] => Array
                (
                    [0] => pet
                    [1] => chk
                    [2] => spo
                    [3] => sen
                    [4] => gos
                    [5] => vas
                    [6] => nov
                )

            [3] => Array
                (
                    [0] => pet
                    [1] => chk
                    [2] => spo
                    [3] => sen
                    [4] => gos
                    [5] => dvo
                    [6] => isa
                    [7] => nov
                )

            [4] => Array
                (
                    [0] => pet
                    [1] => chk
                    [2] => spo
                    [3] => sen
                    [4] => gos
                    [5] => let
                    [6] => dvo
                    [7] => isa
                    [8] => nov
                )

            [5] => Array
                (
                    [0] => pet
                    [1] => chk
                    [2] => spo
                    [3] => sen
                    [4] => vla
                    [5] => gos
                    [6] => vas
                    [7] => nov
                )

            [6] => Array
                (
                    [0] => pet
                    [1] => chk
                    [2] => spo
                    [3] => sen
                    [4] => vla
                    [5] => gos
                    [6] => dvo
                    [7] => isa
                    [8] => nov
                )

            [7] => Array
                (
                    [0] => pet
                    [1] => chk
                    [2] => spo
                    [3] => sen
                    [4] => vla
                    [5] => gos
                    [6] => let
                    [7] => dvo
                    [8] => isa
                    [9] => nov
                )

            [8] => Array
                (
                    [0] => pet
                    [1] => chk
                    [2] => spo
                    [3] => sen
                    [4] => vit
                    [5] => vla
                    [6] => gos
                    [7] => vas
                    [8] => nov
                )

            [9] => Array
                (
                    [0] => pet
                    [1] => chk
                    [2] => spo
                    [3] => sen
                    [4] => vit
                    [5] => vla
                    [6] => gos
                    [7] => dvo
                    [8] => isa
                    [9] => nov
                )

            [10] => Array
                (
                    [0] => pet
                    [1] => chk
                    [2] => spo
                    [3] => sen
                    [4] => vit
                    [5] => vla
                    [6] => gos
                    [7] => let
                    [8] => dvo
                    [9] => isa
                    [10] => nov
                )

            [11] => Array
                (
                    [0] => pet
                    [1] => chk
                    [2] => spo
                    [3] => sen
                    [4] => teh
                    [5] => vit
                    [6] => vla
                    [7] => gos
                    [8] => vas
                    [9] => nov
                )

            [12] => Array
                (
                    [0] => pet
                    [1] => chk
                    [2] => spo
                    [3] => sen
                    [4] => teh
                    [5] => vit
                    [6] => vla
                    [7] => gos
                    [8] => dvo
                    [9] => isa
                    [10] => nov
                )

            [13] => Array
                (
                    [0] => pet
                    [1] => chk
                    [2] => spo
                    [3] => sen
                    [4] => teh
                    [5] => vit
                    [6] => vla
                    [7] => gos
                    [8] => let
                    [9] => dvo
                    [10] => isa
                    [11] => nov
                )

            [14] => Array
                (
                    [0] => pet
                    [1] => gor
                    [2] => gos
                    [3] => vas
                    [4] => nov
                )

            [15] => Array
                (
                    [0] => pet
                    [1] => gor
                    [2] => gos
                    [3] => sen
                    [4] => ras
                    [5] => nov
                )

            [16] => Array
                (
                    [0] => pet
                    [1] => gor
                    [2] => gos
                    [3] => sen
                    [4] => spo
                    [5] => vas
                    [6] => nov
                )

            [17] => Array
                (
                    [0] => pet
                    [1] => gor
                    [2] => gos
                    [3] => dvo
                    [4] => isa
                    [5] => nov
                )

            [18] => Array
                (
                    [0] => pet
                    [1] => gor
                    [2] => gos
                    [3] => let
                    [4] => dvo
                    [5] => isa
                    [6] => nov
                )

            [19] => Array
                (
                    [0] => pet
                    [1] => gor
                    [2] => gos
                    [3] => vla
                    [4] => sen
                    [5] => ras
                    [6] => nov
                )

            [20] => Array
                (
                    [0] => pet
                    [1] => gor
                    [2] => gos
                    [3] => vla
                    [4] => sen
                    [5] => spo
                    [6] => vas
                    [7] => nov
                )

            [21] => Array
                (
                    [0] => pet
                    [1] => gor
                    [2] => gos
                    [3] => vla
                    [4] => vit
                    [5] => sen
                    [6] => ras
                    [7] => nov
                )

            [22] => Array
                (
                    [0] => pet
                    [1] => gor
                    [2] => gos
                    [3] => vla
                    [4] => vit
                    [5] => sen
                    [6] => spo
                    [7] => vas
                    [8] => nov
                )

            [23] => Array
                (
                    [0] => pet
                    [1] => gor
                    [2] => gos
                    [3] => vla
                    [4] => vit
                    [5] => teh
                    [6] => sen
                    [7] => ras
                    [8] => nov
                )

            [24] => Array
                (
                    [0] => pet
                    [1] => gor
                    [2] => gos
                    [3] => vla
                    [4] => vit
                    [5] => teh
                    [6] => sen
                    [7] => spo
                    [8] => vas
                    [9] => nov
                )

        )

    [travel time] => Array
        (
            [0] => 34
            [1] => 30
            [2] => 41
            [3] => 40
            [4] => 47
            [5] => 49
            [6] => 48
            [7] => 55
            [8] => 50
            [9] => 49
            [10] => 56
            [11] => 53
            [12] => 52
            [13] => 59
            [14] => 27
            [15] => 22
            [16] => 40
            [17] => 26
            [18] => 33
            [19] => 30
            [20] => 48
            [21] => 31
            [22] => 49
            [23] => 34
            [24] => 52
        )

)
Array
(
    [0] => pet
    [1] => gor
    [2] => gos
    [3] => sen
    [4] => ras
    [5] => nov
)
Начальная точка: ст. м. Петроградская
Из нее едешь на метро до точки ст. м. Горьковская 3 мин
Из нее едешь на метро до точки Гостиный Двор 6 мин
Из нее едешь на метро до точки Сенная Площадь 3 мин
Из нее идешь пешком до точки Дом Раскольникова 3 мин
Из нее едешь на автобусе до точки Новая Голландия 7 мин
В итоге ты попадешь в точку Новая Голландия за 22 минут