Задача 21. Кратчайший путь ≡

Условие

Двум друзьям нужно добраться до общежития. Комендантский час начинается в 23:00, а сейчас на часах 22:40. Им нужно успеть добежать до общежития как можно скорее.

На их пути есть несколько последовательностей перекрестков, по которым они могут пройти. Но только одна последовательность будет кратчайшей. Нужно помочь друзьям найти кратчайший путь и добраться до общежития, которое находится на одном из перекрестков вовремя.

Формат входных данных

На вход подается число N, S и E .

N - количество перекрестков.

S - начальный перекресток.

E - конечный перекресток.

После чисел следует матрица смежности графа размерностью N с расстоянием от одного перекрестка до следующего.

Формат выходных данных

Вывести длину минимального пути.

Ограничения

3 ≤ N ≤ 16

0 ≤ S ≤ 15

0 ≤ E ≤ 15

Примеры тестов

10 4 6
0 407 405 152 0 0 362 0 0 0
407 0 213 0 15 0 185 0 116 136
405 213 0 350 19 0 385 0 0 0
152 0 350 0 449 391 467 201 0 0
0 15 19 449 0 0 0 0 0 77
0 0 0 391 0 0 0 0 258 444
362 185 385 467 0 0 0 463 254 388
0 0 0 201 0 0 463 0 141 0
0 116 0 0 0 258 254 141 0 284
0 136 0 0 77 444 388 0 284 0
            

391