Описание

Ограничение по времени: 1000 ms
Ограничение по памяти: 256 Mb

Ответы на вопросы

Задача: Проложи дорогу

Правительство некоторой всем известной страны решило глобально перестроить дорожную систему – оно уже успело разрушить все дороги, и теперь нужно выстроить дорожную сеть заново. Новые двусторонние дороги можно строить между любыми двумя городами, и стоимость постройки дороги равна расстоянию между соответствующими городами. Однако в некоторых случаях ландшафт позволяет построить дорогу за другую цену, такие пары городов называются особыми. Правительство решило первым делом соединить два главных города данной страны – А и Б. Вам поручили разработать план постройки дорог, при котором суммарная стоимость всех построенных дорог будет минимально возможной, и при этом по построенным дорогам можно будет добраться из города А в город Б.

Входные данные
Первая строка содержит число N – количество городов в стране (\(1\leq N\leq10^4\)). Каждая из последующих N строк содержит по два целых числа, xi и yi – координаты соответствующего города (\(|x|, |y| \leq 10^6\) ). Далее содержится число M – количество особых пар городов (\(0\leq M \leq min(10^4, N(N-1)/2)\). Далее в M строках содержится описание особых дорог, каждое состоит из трех целых чисел: u, v – пара различных городов, между которыми проходит особая дорога, и w – стоимости постройки соответствующей дороги (\(1 \leq u,v \leq N, 0 \leq w \leq 10^6\)). В последней строке содержатся номера городов А и Б (от 1 до N).

Выходные данные
Выведите одно число – искомую минимальную длину. Ваш ответ должен отличаться от правильного не более чем на 10−5.
 

Ввод Вывод
4
1 1
0 0
1 0
0 1
1
1 2 100
2 1
2.0000000000


Прикрепите файл с исходным кодом программы:
     
или введите исходный код на языке:


Правила оформления программ и список ошибок при автоматической проверке задач
           

Ваш ответ:

Загруженные файлы:


Нет

Примечание учителя: