Правительство некоторой всем известной страны решило глобально перестроить дорожную систему – оно уже успело разрушить все дороги, и теперь нужно выстроить дорожную сеть заново. Новые двусторонние дороги можно строить между любыми двумя городами, и стоимость постройки дороги равна расстоянию между соответствующими городами (здесь понимается расстояние между точками на плоскости). Однако в некоторых случаях ландшафт вынуждает построить дорогу за другую цену, такие пары городов называются особыми. Правительство решило первым делом соединить два главных города данной страны – А и Б. Вам поручили разработать план постройки дорог, при котором суммарная стоимость всех построенных дорог будет минимально возможной, и при этом по построенным дорогам можно будет добраться из города А в город Б.
Первая строка содержит число \(N\) – количество городов в стране (\(1 \leq N \leq 10^4\)). Каждая из последующих \(N\) строк содержит по два целых числа, \(x_i\) и \(y_i\) – координаты соответствующего города (\(|x_i|, |y_i| \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
Вам дано описание дорожной сети страны. Ваша задача – найти длину кратчайшего пути между городами А и B.
Сеть дорог задана во входном файле следующим образом: первая строка содержит числа \(N\) и \(K\) (\(1 \leq N \leq 100000\), \(0 \leq K \leq 300000\)), где \(K\) – количество дорог. Каждая из следующих \(K\) строк содержит описание дороги с двусторонним движением – три целых числа \(a_i\), \(b_i\) и \(l_i\) (\(1 \leq a_i,b_i \leq N\), \(1 \leq l_i \leq 10^6\)). Это означает, что имеется дорога длины \(l_i\), которая ведет из города \(a_i\) в город \(b_i\). В последней строке находятся два числа \(А\) и \(В\) – номера городов, между которыми надо посчитать кратчайшее расстояние (\(1 \leq A, B \leq N\))
Вы должны вывести в выходной файл единственное число – расстояние между требуемыми городами. Если по дорогам от города \(А\) до города \(В\) доехать невозможно, выведите –1.
6 4 1 2 7 2 4 8 4 5 1 4 3 100 3 1
115
Дан ориентированный взвешенный граф.
Найдите кратчайшее расстояние от одной заданной вершины до другой.
В первой строке входного файла два числа: N и M (1 ≤ N ≤ 100, 1 ≤ M ≤ 10000), где N - количество вершин графа, а M - количество ребер.
В следующей строке заданы числа S и F - начальная и конечная вершины.
Далее следует \(M\) троек чисел Ai, Bi, Ti (1 ≤ Ti ≤ 10) - номера вершин соединенных ребром и вес данного ребра.
Вывести искомое расстояние или -1, если пути между указанными вершинами не существует.
3 6 2 1 1 2 1 1 3 1 2 1 4 2 3 1 3 1 2 3 2 1
3
На день рождения юному технику Мише подарили машинку с радиоуправлением. Мише быстро наскучило гонять машинку туда-сюда по комнате, и он соорудил специальную трассу. Для этого он разбил комнату на квадратные ячейки, некоторые из них оставив пустыми, а в некоторые поставив препятствия. Целую неделю Миша каждый день улучшал свой рекорд по прохождению трассы. Но каково же было разочарование Миши, когда к нему в гости пришел Тима со своей машинкой и побил его рекорд. Стало понятно, что машинку необходимо модернизировать.
На пробных испытаниях, которые были произведены через день, Миша обнаружил, что машинка действительно ездит лучше, однако ее поведение несколько изменилось. На пульте теперь функционируют только четыре кнопки: вперед, назад, вправо, влево. При нажатии на них машинка едет по направлению к соответствующей стене комнаты, являющейся одновременно границей трассы, точно перпендикулярно ей. Машинка разгоняется до такой скорости, что перестает реагировать на другие команды, врезается в ближайшее препятствие или стену и отскакивает от нее на половину пройденного расстояния, то есть если между машинкой и стеной было x пустых клеток, то после отскока она остановится на клетке, от которой 
клеток до стены (⌊ x⌋ означает округление вниз, например 
, 
).
Теперь Мише интересно, какое минимальное количество раз необходимо нажать на кнопку пульта, чтобы машинка, начав в клетке старта, остановилась в клетке финиша.
Первая строка входного файла содержит два целых числа n и m — размеры трассы (2 ≤ m, n ≤ 20). Следующие n строк содержат по m символов каждая: символ «.» соответствует пустой клетке, «#» — препятствию, а «S» и «T» — клетке старта и клетке финиша соответственно.
В выходной файл выведите минимальное количество нажатий на кнопки пульта для проведения машинки по трассе от старта до финиша.
Если доехать от старта до финиша невозможно, выведите - 1.
5 5 S#..T .#.## ..... .##.# .#...
6