eolymp
bolt
Try our new interface for solving problems
Məsələlər

Стационарная телефонная сеть

Стационарная телефонная сеть

Мэр города RMR хочет создать безопасную телефонную сеть для использования в экстренных ситуациях в случае серьезных бедствий, когда город будет отрезан от внешнего мира. Некоторые пары зданий в городе могут быть напрямую связаны телефонным проводом. Инженеры муниципалитета подготовили оценку стоимости подключения любой такой пары. Мэр нуждается в Вашей помощи - ему следует построить самую дешевую сеть, соединяющую все здания в городе и удовлетворяющую мерам безопасности, которые изложены далее. Звонок из здания $A$ в другое здание $B$ должен совершаться по простому пути (который не содержит повторяющихся зданий). Существует несколько небезопасных зданий, в которых живут люди с криминальной историей. Мэр хочет чтобы к этим зданиям был только доступ из сети. То есть никакое соединение между зданиями $A$ и $B$ не должно проходить через небезопасное здание $C$ в сети (где $C$ отлично от $A$ и $B$). \InputFile Первая строка содержит три целых числа $n, m, p$, где $n~(1 \le n \le 1000)$ --- количество домов, $m~(0 \le m \le 10^5)$ --- количество возможных прямых соединений между парами домов, а $p~(0 \le p \le n)$ --- количество небезопасных зданий. Здания пронумерованы от $1$ до $n$. Вторая строка содержит $p$ различных целых чисел от $1$ до $n$ (включительно) --- номера небезопасных зданий. Каждая из следующих $m$ строк содержит три целых числа $x_i, y_i$ и $l_i$ описывающих одну потенциальную прямую линию, где $x_i$ и $y_i~(1 \le x_i, y_i \le n)$ --- различные номера зданий, которые она соединяет, а $l_i~(1 \le l_i \le 10000)$ --- стоимость соединения этих зданий. Между любыми двумя городами существует не более одного прямого соединения. \OutputFile Выведите стоимость самой дешевой сети, удовлетворяющей по возможности условиям безопасности. Иначе выведите "\textbf{impossible}". \includegraphics{https://static.e-olymp.com/content/d2/d22330092a2b7d38687dfbd6b7fb73997f1275ef.gif}
Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
4 6 1
1
1 2 1
1 3 1
1 4 1
2 3 2
2 4 4
3 4 3
Çıxış verilənləri #1
6
Giriş verilənləri #2
4 3 2
1 2
1 2 1
2 3 7
3 4 5
Çıxış verilənləri #2
impossible
Mənbə 2014 ACM North America - Rocky Mountain, Problem F