Задача Traceroute. Локальна мережа являє собою N серверів. Деякі пари серверів з’єднані виділеними лініями. Для кожної виділеної лінії відомий час проходження інформації (однаковий в обидва боки). Зрозуміло, що інформація між будь-якими серверами завжди передається якнайшвидше. Адміністратор мережі планує профілактичні роботи, тому кожного дня рівно одна виділена лінія буде від’єднана від мережі. Допоможіть користувачам визначити час отримання інформаціі під час робіт.

Технічні умови.

Програма Traceroute читає з клавіатури через пропуск кількість серверів N, номери серверів, з якого і на який передається інформація A, B (2≤N≤2000,1≤A,B≤N,A<>B). Наступні N рядків містять опис локальної мережі. У i-му рядку на j-й позиції записано час проходження інформації від i-го до j-го сервера – натуральне число від 1 до 100000. Якщо між i-м та j-м серверами немає виділеної лінії, записується 0. Наступний рядок містить натуральне число K (2≤K≤N) – кількість вершин у найкоротшому шляху, далі через пропуск K чисел a=v[1], v[2],,v[K]=bнайкоротший шлях. Програма виводить на екран через пропуск K-1 число – час отримання інформації, якщо виділену лінію від v[i] до v[i+1] буде відключено (1≤i<K). Якщо користувач не зможе отримати інформацію, вивести  -1.  

 

Приклад

Введення

5 1 5

0 1 0 0 0

1 0 3 0 100

0 3 0 3 5

0 0 3 0 3

0 100 5 3 0

4 1 2 3 5

Виведення

-1 101 10 

 

Малюнок до прикладу

 

© LIKT 1998-2018