Задача №112841. Декартово
Государство Иксово состоит из N x городов, некоторые пары которых связаны дорогами с двусторонним движением. Каждая дорога имеет свою длину. Всего межгородских дорог в стране Mx, при чем известно, что из каждого города Иксевщины можно доехать по дорогам до каждого другого города этой страны. Города Иксово пронуменрованы натуральными числами от 1 до N x .
Государство Игреково состоит из N y городов, некоторые пары которых связаны дорогами с двусторонним движением. Каждая дорога имеет свою длину. Всего межгородских дорог в стране M y , при чем известно, что из каждого города Игреково можно доехать по дорогам до каждого другого города этой страны. Города Игреково пронуменрованы натуральными числами от 1 до N y .
Страна Декартово состоит из N = N x · N y городов: каждому городу Декартово во взаимно однозначное соответствие можно поставить пару городов-побратимов ( x , y ) , где x — город Иксово, а y — город Игреково. Некоторые пары городов Декартово также соединены дорогами с двусторонним движением. Дорог в стране ровно M = N x · M y + N y · M x . При этом дорога между городами ( x 1 , y 1 ) и ( x 2 , y 2 ) существует только в одном из таких двух случаев:
- Если x 1 = x 2 , а между городами y 1 и y 2 Игреково проложена дорога. При этом длина дороги между городами ( x , y 1 ) и ( x , y 2 ) Декартово равно длине дороги между городами y 1 и y 2 Игреково.
- Если y 1 = y 2 , а между городами x 1 и x 2 Иксевщены проложена дорога. При этом длина дороги между городами ( x 1 , y ) и ( x 2 , y ) Декартово равно длине дороги между городами x 1 и x 2 Иксево.
Данная задача состоит из двух подзадач. В обеих подзадачах всю информацию про соединение дорогами задано во входных файлах.
- В первой подзадаче требуется определить длину самого короткого пути по дорогам Декартовщины из города (1, 1) в город ( N x , N y ) .
- Во второй подзадаче некоторые дороги Декартовщины требуется закрыть. Ваша задача — определить, дороги какой наименьшей суммарной длины можно оставить в Декартовщине, чтобы из любого ее города все еще можно было попасть в любой другой. Напишите программу cartesius, которая решает эти подзадачи.
Первая строка входного файла содержит номер подзадачи, которую требуется решить ( 1 или 2 ). Вторая строка содержит натуральные числа N x и M x (1 ≤ N x ≤ 5·10 4 , 1 ≤ M x ≤ 5·10 4 ) "— количество городов и дорог в Иксово. В последующих M x строках описаны дороги Иксово: в каждой строке по три числа, где первые два задают номера разных городов, соедененных дорогой, а третья есть длиной соответствующей дороги (натуральное число, которое не превышает 10 7 ).
В следующей строке входного файла указаны натуральные числа N y и M y (1 ≤ N y ≤ 5·10 4 , 1 ≤ M y ≤ 5·10 4 ) — количество городов и дорог в Игреково. Последующие M y строк содержат описание дорог Игреково; формат данных и ограничения соответствуют описанным выше.
Выходной файл должен содержать единственно целое число — ответ на вопрос подзадачи.
Набор тестов состоит из 4 блоков, для которых дополнительно выполняются такие условия:
- 12 баллов: номер подзадачи — 1 , числа N x , M x , N y , M y не превышают 200 .
- 28 баллов: номер подзадачи — 1 , дополнительных ограничений нет.
- 12 баллов: номер подзадачи — 2 , числа N x , M x , N y , M y не превышают 200 .
- 48 баллов: номер подзадачи — 2 , дополнительных ограничений нет.
1 3 2 2 1 15 3 1 14 3 2 2 1 15 3 2 15
44
2 3 2 2 1 15 3 1 14 3 2 2 1 15 3 2 15
117