fork(1) 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 = 'kre'; // Петроградская
  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, SUBWAY),
  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. {
  140.     return array(
  141.         'time' => $time,
  142.         'by' => $byWhat
  143.     );
  144. }
  145.  
  146. /*заполняем массив, который будет содержать метки для каждой из вершин а также
  147. массив, в котором ведем учет уже проверенных вершин и массив, в который сохраняем отрезки пути */
  148.  
  149. $unChecked = array();
  150. $marks     = array();
  151. $roads     = array();
  152.  
  153. foreach ($paths as $point => $details) {
  154.     static $i = 999;
  155.     if ($point == $startPoint) {
  156.         $marks[$point] = 0;
  157.         $roads[$point] = "Из {$pointNames[$point]}";
  158.     } else {
  159.         $marks[$point] = $i++;
  160.     }
  161.     $unChecked[$point] = $marks[$point];
  162. }
  163.  
  164. //echo "Starting from $startPoint... Destination : {$endPoint}\n";
  165.  
  166. while (!empty($unChecked)) {
  167.     $unCheckedR = array_flip($unChecked);
  168.     $min        = min(array_keys($unCheckedR));
  169.     $curr       = $unCheckedR[$min];
  170.   //  echo "Now curr is {$curr}\n";
  171.     unset($unChecked[$curr]);
  172.     $neighbours = $paths[$curr];
  173.  
  174.   //  echo "Neighbours are: ";
  175.    // var_dump($neighbours);
  176.   //  echo "\n";
  177.  
  178.     foreach ($neighbours as $station => $details) {
  179.     //  echo "Starting cicle...\n";
  180.     //  echo "neighbour is {$station}\n";
  181.       //  echo "it's mark is {$marks[$station]}, curr's mark is {$marks[$curr]} (expecting 0).\n";
  182.         if (($details["time"] + $marks[$curr]) <= $marks[$station]) {
  183.         //  echo "TRUE!\n";
  184.             $unChecked[$station] = $marks[$station] = $details["time"] + $marks[$curr];
  185.          //  echo "time is {$details['time']}, {$station}\'s new mark is {$marks[$station]}.\n";
  186.             $transport       = $details["by"];
  187.  
  188.             $roads[$station] = "{$roads[$curr]} {$transportName[$transport]} до {$pointNames[$station]} - {$details['time']} минут.\n";
  189.             $roads[$station] .= ($station == $endPoint) ? "В итоге ты попадаешь в точку {$pointNames[$station]} за {$marks[$station]} минут.\n" : "Из неё";
  190.         }
  191.      // echo "now endPoint's mark is {$marks[$endPoint]}, endPoint's road is {$roads[$endPoint]}.\n";
  192.     }
  193.    // print_r($unChecked);
  194.    //var_dump($roads[$endPoint]);
  195.   // echo "deleting curr...\n";
  196. }
  197.  
  198. echo $roads[$endPoint];
  199.  
Success #stdin #stdout 0.01s 20520KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Из Петропавловская крепость идешь пешком до ст. м. Горьковская - 5 минут.
Из неё едешь на метро до Гостиный Двор - 6 минут.
Из неё едешь на метро до Сенная Площадь - 3 минут.
Из неё идешь пешком до Дом Раскольникова - 3 минут.
Из неё едешь на автобусе до Новая Голландия - 7 минут.
В итоге ты попадаешь в точку Новая Голландия за 24 минут.
https://ideone.com/PfQWQA
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!