fork 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   = 'chk'; // Новая Голландия
  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, BUS),
  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...\n";
  165.  
  166. while (!empty($unChecked)) {
  167.     $unCheckedR = array_flip($unChecked);
  168.     $min        = min(array_keys($unCheckedR));
  169.     $curr       = $unCheckedR[$min];
  170.     unset($unChecked[$curr]);
  171.     $neighbours = $paths[$curr];
  172.  
  173.     echo "Neighbours are: ";
  174.     var_dump($neighbours);
  175.     echo "\n";
  176.  
  177.     foreach ($neighbours as $station => $details) {
  178.     	echo "Starting cicle...\n";
  179.     	echo "neighbour is {$station}\n";
  180.         echo "it's mark is {$marks[$station]}, curr's mark is {$marks[$curr]} (expecting 0).\n";
  181.         if (($details["time"] + $marks[$curr]) <= $marks[$station]) {
  182.         	echo "in\n";
  183.             $marks[$station] = $details["time"] + $marks[$curr];
  184.             echo "time is {$details['time']}, new mark is {$marks[$station]}.\n";
  185.             $transport       = $details["by"];
  186.  
  187.             $roads[$station] = "{$roads[$curr]} {$transportName[$transport]} до {$pointNames[$station]} - {$details['time']} минут.\n";
  188.             $roads[$station] .= ($station == $endPoint) ? "В итоге ты попадаешь в точку {$pointNames[$station]} за {$marks[$station]} минут.\n" : "Из неё";
  189.         }
  190.     }
  191.    // print_r($unChecked);
  192.    //var_dump($roads[$endPoint]);
  193. }
  194.  
  195. echo $roads[$endPoint];
  196.  
Success #stdin #stdout #stderr 0.01s 20520KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Starting from kre...
Neighbours are: array(1) {
  ["gor"]=>
  array(2) {
    ["time"]=>
    int(5)
    ["by"]=>
    string(4) "foot"
  }
}

Starting cicle...
neighbour is gor
it's mark is 1001, curr's mark is 0 (expecting 0).
in
time is 5, new mark is 5.
Neighbours are: array(2) {
  ["chk"]=>
  array(2) {
    ["time"]=>
    int(10)
    ["by"]=>
    string(3) "bus"
  }
  ["gor"]=>
  array(2) {
    ["time"]=>
    int(3)
    ["by"]=>
    string(3) "sub"
  }
}

Starting cicle...
neighbour is chk
it's mark is 1000, curr's mark is 999 (expecting 0).
Starting cicle...
neighbour is gor
it's mark is 5, curr's mark is 999 (expecting 0).
Neighbours are: array(2) {
  ["pet"]=>
  array(2) {
    ["time"]=>
    int(10)
    ["by"]=>
    string(3) "bus"
  }
  ["spo"]=>
  array(2) {
    ["time"]=>
    int(3)
    ["by"]=>
    string(3) "sub"
  }
}

Starting cicle...
neighbour is pet
it's mark is 999, curr's mark is 1000 (expecting 0).
Starting cicle...
neighbour is spo
it's mark is 1002, curr's mark is 1000 (expecting 0).
Neighbours are: array(3) {
  ["pet"]=>
  array(2) {
    ["time"]=>
    int(3)
    ["by"]=>
    string(3) "bus"
  }
  ["kre"]=>
  array(2) {
    ["time"]=>
    int(5)
    ["by"]=>
    string(4) "foot"
  }
  ["gos"]=>
  array(2) {
    ["time"]=>
    int(6)
    ["by"]=>
    string(3) "sub"
  }
}

Starting cicle...
neighbour is pet
it's mark is 999, curr's mark is 5 (expecting 0).
in
time is 3, new mark is 8.
Starting cicle...
neighbour is kre
it's mark is 0, curr's mark is 5 (expecting 0).
Starting cicle...
neighbour is gos
it's mark is 1009, curr's mark is 5 (expecting 0).
in
time is 6, new mark is 11.
Neighbours are: array(3) {
  ["chk"]=>
  array(2) {
    ["time"]=>
    int(3)
    ["by"]=>
    string(3) "sub"
  }
  ["vas"]=>
  array(2) {
    ["time"]=>
    int(10)
    ["by"]=>
    string(3) "bus"
  }
  ["sen"]=>
  array(2) {
    ["time"]=>
    int(7)
    ["by"]=>
    string(3) "sub"
  }
}

Starting cicle...
neighbour is chk
it's mark is 1000, curr's mark is 1002 (expecting 0).
Starting cicle...
neighbour is vas
it's mark is 1003, curr's mark is 1002 (expecting 0).
Starting cicle...
neighbour is sen
it's mark is 1010, curr's mark is 1002 (expecting 0).
in
time is 7, new mark is 1009.
Neighbours are: array(3) {
  ["spo"]=>
  array(2) {
    ["time"]=>
    int(10)
    ["by"]=>
    string(3) "bus"
  }
  ["gos"]=>
  array(2) {
    ["time"]=>
    int(7)
    ["by"]=>
    string(3) "sub"
  }
  ["nov"]=>
  array(2) {
    ["time"]=>
    int(11)
    ["by"]=>
    string(4) "foot"
  }
}

Starting cicle...
neighbour is spo
it's mark is 1002, curr's mark is 1003 (expecting 0).
Starting cicle...
neighbour is gos
it's mark is 11, curr's mark is 1003 (expecting 0).
Starting cicle...
neighbour is nov
it's mark is 1007, curr's mark is 1003 (expecting 0).
Neighbours are: array(2) {
  ["dvo"]=>
  array(2) {
    ["time"]=>
    int(6)
    ["by"]=>
    string(4) "foot"
  }
  ["gos"]=>
  array(2) {
    ["time"]=>
    int(7)
    ["by"]=>
    string(4) "foot"
  }
}

Starting cicle...
neighbour is dvo
it's mark is 1005, curr's mark is 1004 (expecting 0).
Starting cicle...
neighbour is gos
it's mark is 11, curr's mark is 1004 (expecting 0).
Neighbours are: array(3) {
  ["isa"]=>
  array(2) {
    ["time"]=>
    int(6)
    ["by"]=>
    string(4) "foot"
  }
  ["gos"]=>
  array(2) {
    ["time"]=>
    int(6)
    ["by"]=>
    string(4) "foot"
  }
  ["let"]=>
  array(2) {
    ["time"]=>
    int(6)
    ["by"]=>
    string(4) "foot"
  }
}

Starting cicle...
neighbour is isa
it's mark is 1006, curr's mark is 1005 (expecting 0).
Starting cicle...
neighbour is gos
it's mark is 11, curr's mark is 1005 (expecting 0).
Starting cicle...
neighbour is let
it's mark is 1004, curr's mark is 1005 (expecting 0).
Neighbours are: array(2) {
  ["dvo"]=>
  array(2) {
    ["time"]=>
    int(6)
    ["by"]=>
    string(4) "foot"
  }
  ["nov"]=>
  array(2) {
    ["time"]=>
    int(5)
    ["by"]=>
    string(4) "foot"
  }
}

Starting cicle...
neighbour is dvo
it's mark is 1005, curr's mark is 1006 (expecting 0).
Starting cicle...
neighbour is nov
it's mark is 1007, curr's mark is 1006 (expecting 0).
Neighbours are: array(3) {
  ["vas"]=>
  array(2) {
    ["time"]=>
    int(11)
    ["by"]=>
    string(4) "foot"
  }
  ["isa"]=>
  array(2) {
    ["time"]=>
    int(5)
    ["by"]=>
    string(4) "foot"
  }
  ["ras"]=>
  array(2) {
    ["time"]=>
    int(7)
    ["by"]=>
    string(3) "bus"
  }
}

Starting cicle...
neighbour is vas
it's mark is 1003, curr's mark is 1007 (expecting 0).
Starting cicle...
neighbour is isa
it's mark is 1006, curr's mark is 1007 (expecting 0).
Starting cicle...
neighbour is ras
it's mark is 1008, curr's mark is 1007 (expecting 0).
Neighbours are: array(2) {
  ["nov"]=>
  array(2) {
    ["time"]=>
    int(7)
    ["by"]=>
    string(3) "bus"
  }
  ["sen"]=>
  array(2) {
    ["time"]=>
    int(3)
    ["by"]=>
    string(4) "foot"
  }
}

Starting cicle...
neighbour is nov
it's mark is 1007, curr's mark is 1008 (expecting 0).
Starting cicle...
neighbour is sen
it's mark is 1009, curr's mark is 1008 (expecting 0).
Neighbours are: array(6) {
  ["vas"]=>
  array(2) {
    ["time"]=>
    int(7)
    ["by"]=>
    string(3) "sub"
  }
  ["sen"]=>
  array(2) {
    ["time"]=>
    int(3)
    ["by"]=>
    string(3) "sub"
  }
  ["dvo"]=>
  array(2) {
    ["time"]=>
    int(6)
    ["by"]=>
    string(4) "foot"
  }
  ["gor"]=>
  array(2) {
    ["time"]=>
    int(6)
    ["by"]=>
    string(3) "sub"
  }
  ["let"]=>
  array(2) {
    ["time"]=>
    int(7)
    ["by"]=>
    string(4) "foot"
  }
  ["vla"]=>
  array(2) {
    ["time"]=>
    int(7)
    ["by"]=>
    string(4) "foot"
  }
}

Starting cicle...
neighbour is vas
it's mark is 1003, curr's mark is 11 (expecting 0).
in
time is 7, new mark is 18.
Starting cicle...
neighbour is sen
it's mark is 1009, curr's mark is 11 (expecting 0).
in
time is 3, new mark is 14.
Starting cicle...
neighbour is dvo
it's mark is 1005, curr's mark is 11 (expecting 0).
in
time is 6, new mark is 17.
Starting cicle...
neighbour is gor
it's mark is 5, curr's mark is 11 (expecting 0).
Starting cicle...
neighbour is let
it's mark is 1004, curr's mark is 11 (expecting 0).
in
time is 7, new mark is 18.
Starting cicle...
neighbour is vla
it's mark is 1011, curr's mark is 11 (expecting 0).
in
time is 7, new mark is 18.
Neighbours are: array(6) {
  ["ras"]=>
  array(2) {
    ["time"]=>
    int(3)
    ["by"]=>
    string(4) "foot"
  }
  ["spo"]=>
  array(2) {
    ["time"]=>
    int(7)
    ["by"]=>
    string(3) "sub"
  }
  ["gos"]=>
  array(2) {
    ["time"]=>
    int(3)
    ["by"]=>
    string(3) "sub"
  }
  ["vla"]=>
  array(2) {
    ["time"]=>
    int(4)
    ["by"]=>
    string(3) "sub"
  }
  ["vit"]=>
  array(2) {
    ["time"]=>
    int(2)
    ["by"]=>
    string(3) "sub"
  }
  ["teh"]=>
  array(2) {
    ["time"]=>
    int(3)
    ["by"]=>
    string(3) "sub"
  }
}

Starting cicle...
neighbour is ras
it's mark is 1008, curr's mark is 14 (expecting 0).
in
time is 3, new mark is 17.
Starting cicle...
neighbour is spo
it's mark is 1002, curr's mark is 14 (expecting 0).
in
time is 7, new mark is 21.
Starting cicle...
neighbour is gos
it's mark is 11, curr's mark is 14 (expecting 0).
Starting cicle...
neighbour is vla
it's mark is 18, curr's mark is 14 (expecting 0).
in
time is 4, new mark is 18.
Starting cicle...
neighbour is vit
it's mark is 1012, curr's mark is 14 (expecting 0).
in
time is 2, new mark is 16.
Starting cicle...
neighbour is teh
it's mark is 1013, curr's mark is 14 (expecting 0).
in
time is 3, new mark is 17.
Neighbours are: array(3) {
  ["sen"]=>
  array(2) {
    ["time"]=>
    int(4)
    ["by"]=>
    string(3) "sub"
  }
  ["gos"]=>
  array(2) {
    ["time"]=>
    int(7)
    ["by"]=>
    string(4) "foot"
  }
  ["vit"]=>
  array(2) {
    ["time"]=>
    int(3)
    ["by"]=>
    string(3) "sub"
  }
}

Starting cicle...
neighbour is sen
it's mark is 14, curr's mark is 18 (expecting 0).
Starting cicle...
neighbour is gos
it's mark is 11, curr's mark is 18 (expecting 0).
Starting cicle...
neighbour is vit
it's mark is 16, curr's mark is 18 (expecting 0).
Neighbours are: array(3) {
  ["sen"]=>
  array(2) {
    ["time"]=>
    int(2)
    ["by"]=>
    string(3) "sub"
  }
  ["teh"]=>
  array(2) {
    ["time"]=>
    int(2)
    ["by"]=>
    string(3) "sub"
  }
  ["vla"]=>
  array(2) {
    ["time"]=>
    int(3)
    ["by"]=>
    string(3) "sub"
  }
}

Starting cicle...
neighbour is sen
it's mark is 14, curr's mark is 16 (expecting 0).
Starting cicle...
neighbour is teh
it's mark is 17, curr's mark is 16 (expecting 0).
Starting cicle...
neighbour is vla
it's mark is 18, curr's mark is 16 (expecting 0).
Neighbours are: array(2) {
  ["sen"]=>
  array(2) {
    ["time"]=>
    int(3)
    ["by"]=>
    string(3) "sub"
  }
  ["vit"]=>
  array(2) {
    ["time"]=>
    int(2)
    ["by"]=>
    string(3) "sub"
  }
}

Starting cicle...
neighbour is sen
it's mark is 14, curr's mark is 17 (expecting 0).
Starting cicle...
neighbour is vit
it's mark is 16, curr's mark is 17 (expecting 0).
stderr
copy 
PHP Notice:  Undefined index: spo in /home/HOaMfR/prog.php on line 187
PHP Notice:  Undefined index: chk in /home/HOaMfR/prog.php on line 195
https://ideone.com/I4njoh
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!