Схема дорог
(Время: 1 сек. Память: 128 Мб Сложность: 58%)
Имеется две схемы дорог некоторого N-ского района, в котором ровно N населенных пунктов. Данные схемы были построены независимо, поэтому неизвестно: какие из вершин графа в одной схеме соответствуют вершинам графа другой схемы. Также известно, что схемы дорог представляют собой неориентированный граф.
Первая схема представлена в виде матрицы весов, в которой населенные пункты пронумерованы числами от 1 до N. В i-й строке и j-м столбце записана протяженность дороги (в километрах) между i-м и j-м населенными пунктами.
Вторая схема представлена в виде списка смежности, в котором населенные пункты пронумерованы английскими буквами по алфавиту: A, B, C, D, E, F и так далее. Для каждой вершины перечисляются все смежные ей (соединенные с ней дорогой).
Требуется определить кратчайшее расстояние между двумя пунктами, представленными в формате нумерации во второй схеме.
Входные данные
Первая строка входного файла INPUT.TXT содержит целое число N (6 ≤ N ≤ 9) – количество населенных пунктов в N-ском районе.
Вторая строка входных данных – пустая.
Далее идет N строк по N целых чисел Aij (0 ≤ Aij < 100), разделенных пробелом – матрица весов, описывающая первую схему района. Нулевые значения обозначают отсутствие дороги между городами, ненулевые описывают протяженность дороги в километрах.
Далее идет пустая строка.
Далее идет N строк, каждая из которых содержит информацию о населенном пункте, а именно то, с какими пунктами он соединен дорогой. Первая строка данного набора задает смежные вершины для пункта A, вторая – для пункта B, третья – для пункта C и так далее. Смежные вершины (населенные пункты) обозначаются прописными буквами английского алфавита, следуют в алфавитном порядке без разделителя.
Далее идет пустая строка.
Далее идет информация о двух населенных пунктах – два английских символа, разделенные пробелом, в формате нумерации во второй схеме, обозначающих пункты, кратчайшее расстояние между которыми необходимо найти. Гарантируется, что путь между заданными пунктами существует и ответ однозначен.
Выходные данные
В выходной файл OUTPUT.TXT выведите целое число – наикратчайшее расстояние между указанными пунктами.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 6
0 0 5 1 0 0
0 0 6 0 2 0
5 6 0 3 0 3
1 0 3 0 4 0
0 2 0 4 0 0
0 0 3 0 0 0
CD
CDEF
ABE
AB
BC
B
F E | 7 |
Пояснение к примеру
В примере описаны следующие схемы дорог:
Слева представлена первая схема, справа – вторая. На основании этих данных можно однозначно сопоставить нумерацию населенных пунктов в схемах: A – 1, B – 3, C – 4, D – 2, E – 1, F – 6. После переноса данных из первой схемы на граф второй схемы получим:
Теперь становится ясно, что кратчайший путь из F в E в нумерации второй схемы означает поиск кратчайшего пути из вершины 6 в вершину 1 в нумерации первой схемы. Очевидно, что кратчайший маршрут мы можем записать как 6→3→4→1 (первая схема) или F→B→C→E (вторая схема). Суммируя длины дорог в маршруте, получаем, что искомое значение равно 3+3+1 = 7.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
