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

            [time] => 22
        )

    [possible ways] => 32
)
Начальная точка: ст. м. Петроградская
Из нее едешь на метро до точки ст. м. Горьковская 3 мин
Из нее едешь на метро до точки Гостиный Двор 6 мин
Из нее едешь на метро до точки Сенная Площадь 3 мин
Из нее идешь пешком до точки Дом Раскольникова 3 мин
Из нее едешь на автобусе до точки Новая Голландия 7 мин
В итоге ты попадешь в точку Новая Голландия за 22 минут
https://ideone.com/BdyGPI
language:
PHP (php 7.3.5)
created:
5 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!