<?php
/* http://d...content-available-to-author-only...2.net/ */
define ( 'SUBWAY' , "едешь на метро" ) ; define ( 'FOOT' , "идешь пешком" ) ; define ( 'BUS' , "едешь на автобусе" ) ;
/*Функция построения кратчайшего пути.
Возвращает NULL, если кратчайший путь не содержит промежуточных нодов.
Иначе, возвращает массив промежуточных нодов.
*/
function getPath( $start , $end , $interimStep ) {
if ( $interimStep [ $start ] [ $end ] == INF) {
return NULL ;
}
$temp = $end ;
while ( $temp != INF) {
$temp = $interimStep [ $start ] [ $temp ] ;
}
return $shortestPath ;
}
/*Функция вывода пути.
*/
function printPath( $startPoint , $endPoint , $shortestPath , $paths , $pointNames ) {
1 => BUS,
2 => SUBWAY
) ,
0 => BUS,
3 => SUBWAY
) ,
0 => BUS,
5 => FOOT,
11 => SUBWAY
) ,
1 => SUBWAY,
4 => BUS,
12 => SUBWAY
) ,
3 => BUS,
11 => SUBWAY,
9 => FOOT
) ,
2 => FOOT
) ,
7 => FOOT,
11 => FOOT
) ,
8 => FOOT,
11 => FOOT,
6 => FOOT
) ,
7 => FOOT,
9 => FOOT
) ,
4 => FOOT,
8 => FOOT,
10 => BUS
) ,
9 => BUS,
12 => FOOT
) ,
4 => SUBWAY,
12 => SUBWAY,
7 => FOOT,
2 => SUBWAY,
6 => FOOT,
13 => FOOT
) ,
10 => FOOT,
3 => SUBWAY,
11 => SUBWAY,
13 => SUBWAY,
14 => SUBWAY,
15 => SUBWAY
) ,
12 => SUBWAY,
11 => FOOT,
14 => SUBWAY
) ,
12 => SUBWAY,
15 => SUBWAY,
13 => SUBWAY
) ,
12 => SUBWAY,
14 => SUBWAY
)
) ;
echo "Начальная точка: \" {$pointNames [$startPoint ]}\" \n " ;
$temp = $startPoint ;
if ( $shortestPath != NULL ) {
$temp = $startPoint ;
foreach ( $shortestPath as $node ) {
echo "Из нее {$pathTransport [$temp ][$node ]} до точки \" {$pointNames [$node ]}\" {$paths [$temp ][$node ]} мин.\n " ;
$temp = $node ;
}
}
echo "Из нее {$pathTransport [$temp ][$endPoint ]} до точки \" {$pointNames [$endPoint ]}\" {$paths [$temp ][$endPoint ]} мин.\n " ;
echo "В итоге ты попадешь в точку \" {$pointNames [$endPoint ]}\" за {$paths [$startPoint ][$endPoint ]} мин. Приятной поездки!\n \n " ;
}
0 => 'ст. м. Петроградская' ,
1 => 'ст. м. Чкаловская' ,
2 => 'ст. м. Горьковская' ,
3 => 'ст. м. Спортивная' ,
4 => 'ст. м. Василеостровская' ,
5 => 'Петропавловская крепость' ,
6 => 'Летний сад' ,
7 => 'Дворцовая площадь' ,
8 => 'Исакиевский собор' ,
9 => 'Новая Голландия' ,
10 => 'Дом Раскольникова' ,
11 => 'Гостиный Двор' ,
12 => 'Сенная Площадь' ,
13 => 'ст. м. Владимирская' ,
14 => 'Витебский вокзал' ,
15 => 'Технологический Институт'
) ;
1 => 10 ,
2 => 3
) ,
0 => 10 ,
3 => 3
) ,
0 => 3 ,
5 => 5 ,
11 => 6
) ,
1 => 3 ,
4 => 10 ,
12 => 7
) ,
3 => 10 ,
11 => 7 ,
9 => 11
) ,
2 => 5
) ,
7 => 6 ,
11 => 7
) ,
8 => 6 ,
11 => 6 ,
6 => 6
) ,
7 => 6 ,
9 => 5
) ,
4 => 11 ,
8 => 5 ,
10 => 7
) ,
9 => 7 ,
12 => 3
) ,
4 => 7 ,
12 => 3 ,
7 => 6 ,
2 => 6 ,
6 => 7 ,
13 => 7
) ,
10 => 3 ,
3 => 7 ,
11 => 3 ,
13 => 4 ,
14 => 2 ,
15 => 3
) ,
12 => 4 ,
11 => 7 ,
14 => 3
) ,
12 => 2 ,
15 => 2 ,
13 => 3
) ,
12 => 3 ,
14 => 2
)
) ;
$numberOfNodes = count ( $pointNames ) ;
/*Делаем квадратную матрицу путей размера $numberOfNodes, которая будет содержать время кратчайшего пути.
Если путь не существует, то присваиваем ему значение бесконечности.
*/
foreach ( $paths as $i => $array ) {
for ( $j = 0 ; $j < $numberOfNodes ; $j ++ ) {
if ( isset ( $paths [ $i ] [ $j ] ) == NULL ) { $paths [ $i ] [ $j ] = INF;
}
}
}
//Массив, который будет содержать предпоследний шаг кратчайшего пути.
for ( $i = 0 ; $i < $numberOfNodes ; $i ++ ) {
$interimStep [ $i ] = array_fill ( 0 , $numberOfNodes , INF
) ; }
//Алгоритм Флойда-Уоршелла.
for ( $k = 0 ; $k < $numberOfNodes ; $k ++ ) {
for ( $i = 0 ; $i < $numberOfNodes ; $i ++ ) {
for ( $j = 0 ; $j < $numberOfNodes ; $j ++ ) {
if ( ( $paths [ $i ] [ $k ] + $paths [ $k ] [ $j ] ) < $paths [ $i ] [ $j ] ) {
$paths [ $i ] [ $j ] = $paths [ $i ] [ $k ] + $paths [ $k ] [ $j ] ;
$interimStep [ $i ] [ $j ] = $k ;
}
}
}
}
//Тут вылетает предпоследняя нода (дом Раскольникова), но время всего пути выводится корректно.
$startPoint = 0 ; // Петроградская
$endPoint = 9 ; // Новая Голландия
$shortestPath = getPath( $startPoint , $endPoint , $interimStep ) ;
printPath( $startPoint , $endPoint , $shortestPath , $paths , $pointNames ) ;
//ст. м. Петроградская -> Петропавловская крепость
$endPoint = 5 ;
$shortestPath = getPath( $startPoint , $endPoint , $interimStep ) ;
printPath( $startPoint , $endPoint , $shortestPath , $paths , $pointNames ) ;
/*Сенная Площадь -> Новая Голландия
Тут все выводится корректно.
*/
$startPoint = 12 ;
$endPoint = 9 ;
$shortestPath = getPath( $startPoint , $endPoint , $interimStep ) ;
printPath( $startPoint , $endPoint , $shortestPath , $paths , $pointNames ) ;
//Летний сад -> ст. м. Спортивная
$startPoint = 6 ;
$endPoint = 3 ;
$shortestPath = getPath( $startPoint , $endPoint , $interimStep ) ;
printPath( $startPoint , $endPoint , $shortestPath , $paths , $pointNames ) ;
PD9waHAKIAplcnJvcl9yZXBvcnRpbmcoLTEpOwovKiBodHRwOi8vZC4uLmNvbnRlbnQtYXZhaWxhYmxlLXRvLWF1dGhvci1vbmx5Li4uMi5uZXQvICovCiAKZGVmaW5lKCdTVUJXQVknLCAi0LXQtNC10YjRjCDQvdCwINC80LXRgtGA0L4iKTsKZGVmaW5lKCdGT09UJywgItC40LTQtdGI0Ywg0L/QtdGI0LrQvtC8Iik7CmRlZmluZSgnQlVTJywgItC10LTQtdGI0Ywg0L3QsCDQsNCy0YLQvtCx0YPRgdC1Iik7CgovKtCk0YPQvdC60YbQuNGPINC/0L7RgdGC0YDQvtC10L3QuNGPINC60YDQsNGC0YfQsNC50YjQtdCz0L4g0L/Rg9GC0LguCtCS0L7Qt9Cy0YDQsNGJ0LDQtdGCIE5VTEwsINC10YHQu9C4INC60YDQsNGC0YfQsNC50YjQuNC5INC/0YPRgtGMINC90LUg0YHQvtC00LXRgNC20LjRgiDQv9GA0L7QvNC10LbRg9GC0L7Rh9C90YvRhSDQvdC+0LTQvtCyLgrQmNC90LDRh9C1LCDQstC+0LfQstGA0LDRidCw0LXRgiDQvNCw0YHRgdC40LIg0L/RgNC+0LzQtdC20YPRgtC+0YfQvdGL0YUg0L3QvtC00L7Qsi4KKi8KZnVuY3Rpb24gZ2V0UGF0aCgkc3RhcnQsICRlbmQsICRpbnRlcmltU3RlcCl7CiAgICBpZiAoJGludGVyaW1TdGVwWyRzdGFydF1bJGVuZF0gPT0gSU5GKSB7CiAgICAgICAgcmV0dXJuIE5VTEw7CiAgICB9CiAgICAkc2hvcnRlc3RQYXRoID0gYXJyYXkoKTsKICAgICR0ZW1wID0gJGVuZDsKICAgIHdoaWxlICgkdGVtcCAhPSBJTkYpIHsKICAgICAgICAkdGVtcCA9ICRpbnRlcmltU3RlcFskc3RhcnRdWyR0ZW1wXTsKICAgICAgICBhcnJheV91bnNoaWZ0KCRzaG9ydGVzdFBhdGgsICR0ZW1wKTsKICAgIH0KICAgIHVuc2V0KCRzaG9ydGVzdFBhdGhbMF0pOwogICAgcmV0dXJuICRzaG9ydGVzdFBhdGg7Cn0KCi8q0KTRg9C90LrRhtC40Y8g0LLRi9Cy0L7QtNCwINC/0YPRgtC4LgoqLwpmdW5jdGlvbiBwcmludFBhdGgoJHN0YXJ0UG9pbnQsICRlbmRQb2ludCwgJHNob3J0ZXN0UGF0aCwgJHBhdGhzLCAkcG9pbnROYW1lcyl7CgogICAgJHBhdGhUcmFuc3BvcnQgPSBhcnJheSgKICAgICAgICAwICAgPT4gIGFycmF5KAogICAgICAgICAgICAxICAgPT4gIEJVUywKICAgICAgICAgICAgMiAgID0+ICBTVUJXQVkgICAgCiAgICAgICAgICAgICksCgogICAgICAgIDEgICA9PiAgYXJyYXkoCiAgICAgICAgICAgIDAgICA9PiAgQlVTLAogICAgICAgICAgICAzICAgPT4gIFNVQldBWQogICAgICAgICksCgogICAgICAgIDIgICA9PiAgYXJyYXkoCiAgICAgICAgICAgIDAgICA9PiAgQlVTLAogICAgICAgICAgICA1ICAgPT4gIEZPT1QsCiAgICAgICAgICAgIDExICA9PiAgU1VCV0FZCiAgICAgICAgKSwKCiAgICAgICAgMyAgID0+ICBhcnJheSgKICAgICAgICAgICAgMSAgID0+ICBTVUJXQVksCiAgICAgICAgICAgIDQgICA9PiAgQlVTLAogICAgICAgICAgICAxMiAgPT4gIFNVQldBWQogICAgICAgICksCgogICAgICAgIDQgICA9PiAgYXJyYXkoCiAgICAgICAgICAgIDMgICA9PiAgQlVTLAogICAgICAgICAgICAxMSAgPT4gIFNVQldBWSwKICAgICAgICAgICAgOSAgID0+ICBGT09UCiAgICAgICAgKSwKCiAgICAgICAgNSAgID0+ICBhcnJheSgKICAgICAgICAgICAgMiAgID0+ICBGT09UCiAgICAgICAgKSwKCiAgICAgICAgNiAgID0+ICBhcnJheSgKICAgICAgICAgICAgNyAgID0+ICBGT09ULAogICAgICAgICAgICAxMSAgPT4gIEZPT1QKICAgICAgICApLAoKICAgICAgICA3ICAgPT4gIGFycmF5KAogICAgICAgICAgICA4ICAgPT4gIEZPT1QsCiAgICAgICAgICAgIDExICA9PiAgRk9PVCwKICAgICAgICAgICAgNiAgID0+ICBGT09UCiAgICAgICAgKSwKCiAgICAgICAgOCAgID0+ICBhcnJheSgKICAgICAgICAgICAgNyAgID0+ICBGT09ULAogICAgICAgICAgICA5ICAgPT4gIEZPT1QKICAgICAgICApLAoKICAgICAgICA5ICAgPT4gIGFycmF5KAogICAgICAgICAgICA0ICAgPT4gIEZPT1QsCiAgICAgICAgICAgIDggICA9PiAgRk9PVCwKICAgICAgICAgICAgMTAgID0+ICBCVVMKICAgICAgICApLAoKICAgICAgICAxMCAgID0+ICBhcnJheSgKICAgICAgICAgICAgOSAgID0+ICBCVVMsCiAgICAgICAgICAgIDEyICA9PiAgRk9PVAogICAgICAgICksCgogICAgICAgIDExICAgPT4gIGFycmF5KAogICAgICAgICAgICA0ICAgPT4gIFNVQldBWSwKICAgICAgICAgICAgMTIgID0+ICBTVUJXQVksCiAgICAgICAgICAgIDcgICA9PiAgRk9PVCwKICAgICAgICAgICAgMiAgID0+ICBTVUJXQVksCiAgICAgICAgICAgIDYgICA9PiAgRk9PVCwKICAgICAgICAgICAgMTMgID0+ICBGT09UICAgICAgICAKICAgICAgICApLAoKICAgICAgICAxMiAgID0+ICBhcnJheSgKICAgICAgICAgICAgMTAgID0+ICBGT09ULAogICAgICAgICAgICAzICAgPT4gIFNVQldBWSwKICAgICAgICAgICAgMTEgID0+ICBTVUJXQVksCiAgICAgICAgICAgIDEzICA9PiAgU1VCV0FZLAogICAgICAgICAgICAxNCAgPT4gIFNVQldBWSwKICAgICAgICAgICAgMTUgID0+ICBTVUJXQVkKICAgICAgICApLAoKICAgICAgICAxMyAgID0+ICBhcnJheSgKICAgICAgICAgICAgMTIgID0+ICBTVUJXQVksCiAgICAgICAgICAgIDExICA9PiAgRk9PVCwKICAgICAgICAgICAgMTQgID0+ICBTVUJXQVkKICAgICAgICApLAoKICAgICAgICAxNCAgID0+ICBhcnJheSgKICAgICAgICAgICAgMTIgID0+ICBTVUJXQVksCiAgICAgICAgICAgIDE1ICA9PiAgU1VCV0FZLAogICAgICAgICAgICAxMyAgPT4gIFNVQldBWQogICAgICAgICksCgogICAgICAgIDE1ICAgPT4gIGFycmF5KAogICAgICAgICAgICAxMiAgPT4gIFNVQldBWSwKICAgICAgICAgICAgMTQgID0+ICBTVUJXQVkgICAgICAgIAogICAgICAgICkKICAgICk7CiAgICBlY2hvICLQndCw0YfQsNC70YzQvdCw0Y8g0YLQvtGH0LrQsDogXCJ7JHBvaW50TmFtZXNbJHN0YXJ0UG9pbnRdfVwiXG4iOwogICAgJHRlbXAgPSAkc3RhcnRQb2ludDsKICAgIGlmICgkc2hvcnRlc3RQYXRoICE9IE5VTEwpIHsKICAgICAgICAkdGVtcCA9ICRzdGFydFBvaW50OwogICAgICAgIGZvcmVhY2ggKCRzaG9ydGVzdFBhdGggYXMgJG5vZGUpIHsKICAgICAgICAgICAgZWNobyAi0JjQtyDQvdC10LUgeyRwYXRoVHJhbnNwb3J0WyR0ZW1wXVskbm9kZV19INC00L4g0YLQvtGH0LrQuCBcInskcG9pbnROYW1lc1skbm9kZV19XCIgeyRwYXRoc1skdGVtcF1bJG5vZGVdfSDQvNC40L0uXG4iOwogICAgICAgICAgICAkdGVtcCA9ICRub2RlOwogICAgICAgIH0KICAgIH0KICAgIGVjaG8gItCY0Lcg0L3QtdC1IHskcGF0aFRyYW5zcG9ydFskdGVtcF1bJGVuZFBvaW50XX0g0LTQviDRgtC+0YfQutC4IFwieyRwb2ludE5hbWVzWyRlbmRQb2ludF19XCIgeyRwYXRoc1skdGVtcF1bJGVuZFBvaW50XX0g0LzQuNC9LlxuIjsKICAgIGVjaG8gItCSINC40YLQvtCz0LUg0YLRiyDQv9C+0L/QsNC00LXRiNGMINCyINGC0L7Rh9C60YMgXCJ7JHBvaW50TmFtZXNbJGVuZFBvaW50XX1cIiDQt9CwIHskcGF0aHNbJHN0YXJ0UG9pbnRdWyRlbmRQb2ludF19INC80LjQvS4g0J/RgNC40Y/RgtC90L7QuSDQv9C+0LXQt9C00LrQuCFcblxuIjsKfQoKJHBvaW50TmFtZXMgPSBhcnJheSgKICAgIDAgICAgPT4gICfRgdGCLiDQvC4g0J/QtdGC0YDQvtCz0YDQsNC00YHQutCw0Y8nLAogICAgMSAgICA9PiAgJ9GB0YIuINC8LiDQp9C60LDQu9C+0LLRgdC60LDRjycsCiAgICAyICAgID0+ICAn0YHRgi4g0LwuINCT0L7RgNGM0LrQvtCy0YHQutCw0Y8nLAogICAgMyAgICA9PiAgJ9GB0YIuINC8LiDQodC/0L7RgNGC0LjQstC90LDRjycsCiAgICA0ICAgID0+ICAn0YHRgi4g0LwuINCS0LDRgdC40LvQtdC+0YHRgtGA0L7QstGB0LrQsNGPJywKICAgIDUgICAgPT4gICfQn9C10YLRgNC+0L/QsNCy0LvQvtCy0YHQutCw0Y8g0LrRgNC10L/QvtGB0YLRjCcsCiAgICA2ICAgID0+ICAn0JvQtdGC0L3QuNC5INGB0LDQtCcsCiAgICA3ICAgID0+ICAn0JTQstC+0YDRhtC+0LLQsNGPINC/0LvQvtGJ0LDQtNGMJywKICAgIDggICAgPT4gICfQmNGB0LDQutC40LXQstGB0LrQuNC5INGB0L7QsdC+0YAnLAogICAgOSAgICA9PiAgJ9Cd0L7QstCw0Y8g0JPQvtC70LvQsNC90LTQuNGPJywKICAgIDEwICAgPT4gICfQlNC+0Lwg0KDQsNGB0LrQvtC70YzQvdC40LrQvtCy0LAnLAogICAgMTEgICA9PiAgJ9CT0L7RgdGC0LjQvdGL0Lkg0JTQstC+0YAnLAogICAgMTIgICA9PiAgJ9Ch0LXQvdC90LDRjyDQn9C70L7RidCw0LTRjCcsCiAgICAxMyAgID0+ICAn0YHRgi4g0LwuINCS0LvQsNC00LjQvNC40YDRgdC60LDRjycsCiAgICAxNCAgID0+ICAn0JLQuNGC0LXQsdGB0LrQuNC5INCy0L7QutC30LDQuycsCiAgICAxNSAgID0+ICAn0KLQtdGF0L3QvtC70L7Qs9C40YfQtdGB0LrQuNC5INCY0L3RgdGC0LjRgtGD0YInCik7CgokcGF0aHMgPSBhcnJheSgKICAgIDAgICA9PiAgYXJyYXkoCiAgICAgICAgMSAgICA9PiAgMTAsCiAgICAgICAgMiAgICA9PiAgMwogICAgKSwKIAogICAgMSAgID0+ICBhcnJheSgKICAgICAgICAwICAgID0+ICAxMCwKICAgICAgICAzICAgID0+ICAzCiAgICApLAogCiAgICAyICAgPT4gIGFycmF5KAogICAgICAgIDAgICAgPT4gIDMsCiAgICAgICAgNSAgICA9PiAgNSwKICAgICAgICAxMSAgID0+ICA2CiAgICApLAogCiAgICAzICAgPT4gIGFycmF5KAogICAgICAgIDEgICAgPT4gIDMsCiAgICAgICAgNCAgICA9PiAgMTAsCiAgICAgICAgMTIgICA9PiAgNwogICAgKSwKIAogICAgNCAgID0+ICBhcnJheSgKICAgICAgICAzICAgID0+ICAxMCwKICAgICAgICAxMSAgID0+ICA3LAogICAgICAgIDkgICAgPT4gIDExCiAgICApLAogCiAgICA1ICAgPT4gIGFycmF5KAogICAgICAgIDIgICAgPT4gIDUKICAgICksCiAKICAgIDYgICA9PiAgYXJyYXkoCiAgICAgICAgNyAgICA9PiAgNiwKICAgICAgICAxMSAgID0+ICA3CiAgICApLAogCiAgICA3ICAgPT4gIGFycmF5KAogICAgICAgIDggICAgPT4gIDYsCiAgICAgICAgMTEgICA9PiAgNiwKICAgICAgICA2ICAgID0+ICA2CiAgICApLAogCiAgICA4ICAgPT4gIGFycmF5KAogICAgICAgIDcgICAgPT4gIDYsCiAgICAgICAgOSAgICA9PiAgNQogICAgKSwKIAogICAgOSAgID0+ICBhcnJheSgKICAgICAgICA0ICAgID0+ICAxMSwKICAgICAgICA4ICAgID0+ICA1LAogICAgICAgIDEwICAgPT4gIDcKICAgICksCiAKICAgIDEwICAgPT4gIGFycmF5KAogICAgICAgIDkgICAgPT4gIDcsCiAgICAgICAgMTIgICA9PiAgMwogICAgKSwKIAogICAgMTEgICA9PiAgYXJyYXkoCiAgICAgICAgNCAgICA9PiAgNywKICAgICAgICAxMiAgID0+ICAzLAogICAgICAgIDcgICAgPT4gIDYsCiAgICAgICAgMiAgICA9PiAgNiwKICAgICAgICA2ICAgID0+ICA3LAogICAgICAgIDEzICAgPT4gIDcgICAgICAgIAogICAgKSwKIAogICAgMTIgICA9PiAgYXJyYXkoCiAgICAgICAgMTAgICA9PiAgMywKICAgICAgICAzICAgID0+ICA3LAogICAgICAgIDExICAgPT4gIDMsCiAgICAgICAgMTMgICA9PiAgNCwKICAgICAgICAxNCAgID0+ICAyLAogICAgICAgIDE1ICAgPT4gIDMKICAgICksCiAKICAgIDEzICAgPT4gIGFycmF5KAogICAgICAgIDEyICAgPT4gIDQsCiAgICAgICAgMTEgICA9PiAgNywKICAgICAgICAxNCAgID0+ICAzCiAgICApLAogCiAgICAxNCAgID0+ICBhcnJheSgKICAgICAgICAxMiAgID0+ICAyLAogICAgICAgIDE1ICAgPT4gIDIsCiAgICAgICAgMTMgICA9PiAgMwogICAgKSwKIAogICAgMTUgICA9PiAgYXJyYXkoCiAgICAgICAgMTIgICA9PiAgMywKICAgICAgICAxNCAgID0+ICAyICAgICAgICAKICAgICkKKTsKCgoKJG51bWJlck9mTm9kZXMgPSBjb3VudCgkcG9pbnROYW1lcyk7CgovKtCU0LXQu9Cw0LXQvCDQutCy0LDQtNGA0LDRgtC90YPRjiDQvNCw0YLRgNC40YbRgyDQv9GD0YLQtdC5INGA0LDQt9C80LXRgNCwICRudW1iZXJPZk5vZGVzLCDQutC+0YLQvtGA0LDRjyDQsdGD0LTQtdGCINGB0L7QtNC10YDQttCw0YLRjCDQstGA0LXQvNGPINC60YDQsNGC0YfQsNC50YjQtdCz0L4g0L/Rg9GC0LguCtCV0YHQu9C4INC/0YPRgtGMINC90LUg0YHRg9GJ0LXRgdGC0LLRg9C10YIsINGC0L4g0L/RgNC40YHQstCw0LjQstCw0LXQvCDQtdC80YMg0LfQvdCw0YfQtdC90LjQtSDQsdC10YHQutC+0L3QtdGH0L3QvtGB0YLQuC4KKi8KZm9yZWFjaCAoJHBhdGhzIGFzICRpID0+ICRhcnJheSkgewogICAgZm9yICgkaiA9IDA7ICRqIDwgJG51bWJlck9mTm9kZXM7ICRqKyspIHsKICAgICAgICBpZiAoaXNzZXQoJHBhdGhzWyRpXVskal0pID09IE5VTEwpIHsKICAgICAgICAgICAgJHBhdGhzWyRpXVskal0gPSBJTkY7CiAgICAgICAgfQogICAgfQp9CgovL9Cc0LDRgdGB0LjQsiwg0LrQvtGC0L7RgNGL0Lkg0LHRg9C00LXRgiDRgdC+0LTQtdGA0LbQsNGC0Ywg0L/RgNC10LTQv9C+0YHQu9C10LTQvdC40Lkg0YjQsNCzINC60YDQsNGC0YfQsNC50YjQtdCz0L4g0L/Rg9GC0LguCiRpbnRlcmltU3RlcCA9IGFycmF5KCk7CmZvciAoJGkgPSAwOyAkaSA8ICRudW1iZXJPZk5vZGVzOyAkaSsrKSB7CiAgICAkaW50ZXJpbVN0ZXBbJGldID0gYXJyYXlfZmlsbCgwLCAkbnVtYmVyT2ZOb2RlcywgSU5GKTsKfQoKCi8v0JDQu9Cz0L7RgNC40YLQvCDQpNC70L7QudC00LAt0KPQvtGA0YjQtdC70LvQsC4KCmZvciAoJGsgPSAwOyAkayA8ICRudW1iZXJPZk5vZGVzOyAkaysrKSB7CiAgICBmb3IgKCRpID0gMDsgJGkgPCAkbnVtYmVyT2ZOb2RlczsgJGkrKykgewogICAgICAgIGZvciAoJGogPSAwOyAkaiA8ICRudW1iZXJPZk5vZGVzOyAkaisrKSB7CiAgICAgICAgICAgIGlmICgoJHBhdGhzWyRpXVska10gKyAkcGF0aHNbJGtdWyRqXSkgPCAkcGF0aHNbJGldWyRqXSkgewogICAgICAgICAgICAgICAgJHBhdGhzWyRpXVskal0gPSAkcGF0aHNbJGldWyRrXSArICRwYXRoc1ska11bJGpdOwogICAgICAgICAgICAgICAgJGludGVyaW1TdGVwWyRpXVskal0gPSAkazsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KfQoKCgovL9Ci0YPRgiDQstGL0LvQtdGC0LDQtdGCINC/0YDQtdC00L/QvtGB0LvQtdC00L3Rj9GPINC90L7QtNCwICjQtNC+0Lwg0KDQsNGB0LrQvtC70YzQvdC40LrQvtCy0LApLCDQvdC+INCy0YDQtdC80Y8g0LLRgdC10LPQviDQv9GD0YLQuCDQstGL0LLQvtC00LjRgtGB0Y8g0LrQvtGA0YDQtdC60YLQvdC+Lgokc3RhcnRQb2ludCA9IDA7IC8vINCf0LXRgtGA0L7Qs9GA0LDQtNGB0LrQsNGPCiRlbmRQb2ludCA9IDk7IC8vINCd0L7QstCw0Y8g0JPQvtC70LvQsNC90LTQuNGPCiRzaG9ydGVzdFBhdGggPSBnZXRQYXRoKCRzdGFydFBvaW50LCAkZW5kUG9pbnQsICRpbnRlcmltU3RlcCk7CnByaW50UGF0aCgkc3RhcnRQb2ludCwgJGVuZFBvaW50LCAkc2hvcnRlc3RQYXRoLCAkcGF0aHMsICRwb2ludE5hbWVzKTsKCi8v0YHRgi4g0LwuINCf0LXRgtGA0L7Qs9GA0LDQtNGB0LrQsNGPIC0+INCf0LXRgtGA0L7Qv9Cw0LLQu9C+0LLRgdC60LDRjyDQutGA0LXQv9C+0YHRgtGMCiRlbmRQb2ludCA9IDU7CiRzaG9ydGVzdFBhdGggPSBnZXRQYXRoKCRzdGFydFBvaW50LCAkZW5kUG9pbnQsICRpbnRlcmltU3RlcCk7CnByaW50UGF0aCgkc3RhcnRQb2ludCwgJGVuZFBvaW50LCAkc2hvcnRlc3RQYXRoLCAkcGF0aHMsICRwb2ludE5hbWVzKTsKCi8q0KHQtdC90L3QsNGPINCf0LvQvtGJ0LDQtNGMIC0+INCd0L7QstCw0Y8g0JPQvtC70LvQsNC90LTQuNGPCtCi0YPRgiDQstGB0LUg0LLRi9Cy0L7QtNC40YLRgdGPINC60L7RgNGA0LXQutGC0L3Qvi4KKi8KJHN0YXJ0UG9pbnQgPSAxMjsKJGVuZFBvaW50ID0gOTsKJHNob3J0ZXN0UGF0aCA9IGdldFBhdGgoJHN0YXJ0UG9pbnQsICRlbmRQb2ludCwgJGludGVyaW1TdGVwKTsKcHJpbnRQYXRoKCRzdGFydFBvaW50LCAkZW5kUG9pbnQsICRzaG9ydGVzdFBhdGgsICRwYXRocywgJHBvaW50TmFtZXMpOwoKLy/Qm9C10YLQvdC40Lkg0YHQsNC0IC0+INGB0YIuINC8LiDQodC/0L7RgNGC0LjQstC90LDRjwokc3RhcnRQb2ludCA9IDY7CiRlbmRQb2ludCA9IDM7CiRzaG9ydGVzdFBhdGggPSBnZXRQYXRoKCRzdGFydFBvaW50LCAkZW5kUG9pbnQsICRpbnRlcmltU3RlcCk7CnByaW50UGF0aCgkc3RhcnRQb2ludCwgJGVuZFBvaW50LCAkc2hvcnRlc3RQYXRoLCAkcGF0aHMsICRwb2ludE5hbWVzKTs=