#3345

Проложи дорогу (BC)

Темы: [Алгоритм Дейкстры]

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

Входные данные

Первая строка содержит число \(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}\).

Примеры

Входные данные

Выходные данные

2.0000000000

#3347

Кратчайший путь (AB)

Темы: [Куча] [Алгоритм Дейкстры]

Вам дано описание дорожной сети страны. Ваша задача – найти длину кратчайшего пути между городами А и 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.

Примеры

Входные данные

Выходные данные

#3351

Конденсация графа (A)

Темы: [Обход в глубину]

Вам задан связный ориентированный граф с \(N\) вершинами и \(M\) ребрами (\(1 \leq N \leq 20000\), \(1 \leq M \leq 200000\)). Найдите компоненты сильной связности заданного графа и топологически отсортируйте его конденсацию.

Входные данные

Граф задан во входном файле следующим образом: первая строка содержит числа \(N\) и \(M\). Каждая из следующих \(M\) строк содержит описание ребра – два целых числа из диапазона от 1 до \(N\) – номера начала и конца ребра.

Выходные данные

На первой строке выведите число \(K\) – количество компонент сильной связности в заданном графе. На следующей строке выведите \(N\) чисел – для каждой вершины выведите номер компоненты сильной связности, которой принадлежит эта вершина. Компоненты сильной связности должны быть занумерованы таким образом, чтобы для любого ребра номер компоненты сильной связности его начала не превышал номера компоненты сильной связности его конца.

Примеры

Входные данные

Выходные данные

4
3 3 4 3 3 2 1 1 3 2

#3359

Паросочетание

Темы: [Потоки]

Дан двудольный граф, в каждой из долей которого \(N\) вершин. В нем также есть \(M\) ребер, каждое из которых имеет свою стоимость. Требуется найти паросочетание максимальной стоимости.

Входные данные

В первой строке входного файла заданы числа \(1 \leq N \leq 50\) и \(1 \leq M \leq 1000\). В следующих \(M\) строках заданы ребра графа – в каждой по три числа. Первые два из них задают соответственно номера вершин в левой и правой долях, третье – стоимость. Все стоимости не превосходят 10. Гарантируется, что у каждых двух ребер есть отличие хотя бы в одном из концов.

Выходные данные

В первой строке выходного файла выведите максимальную стоимость. В следующей строке выведите \(N\) чисел, i-ое из которых обозначает номер вершины из правой доли, с которой соединена i-ая вершина левой доли. Если i-ая вершина не соединена ни с какой вершиной правой доли, то на i-ом месте должна стоять -1. Из всех возможных ответов нужно вывести наименьший лексикографически. Один ответ считается лексикографически меньшим другого, если первое число, в котором они отличаются у него меньше.

Примеры

Входные данные

Выходные данные

4
-1 1 2

#3360

Авиалинии

Темы: [Обход в глубину]

Компоненты сильной связности

В Берляндии скоро появятся свои авиалинии. Комитет по разработке берляндских авиалиний уже предложил свой вариант соединения городов авиарейсами. Каждый авиарейс задается парой различных городов. Рейсы односторонние. Президенту понравился план, однако он показался ему чересчур неэкономным. Требуется разработать новый план, который содержит наименьшее количество авиарейсов и удовлетворяет условию: если из города a можно было попасть в город b (возможно, с пересадками) согласно первоначальному плану, то и в новом плане это должно быть возможным. Если же это было сделать невозможно, то и согласно новому плану это не должно быть возможным. Очевидно, что из любого города можно попасть в него самого.

Входные данные

В первой строке входного файла записаны целые числа \(N\) и \(M\) (\(1 \leq N \leq 1000\), \(0 \leq M \leq 10000\)), где \(N\) – количество городов в стране, а \(M\) – количество авиарейсов в первоначальном плане. Города нумеруются от 1 до \(N\). Далее записано \(M\) пар различных чисел \(a_i\), \(b_i\) обозначающих наличие рейса из \(a_i\) в \(b_i\) в первоначальном плане (\(1 \leq a_i \leq N\), \(1 \leq b_i \leq N\)). Пары разделяются пробелами или переводами строк. Между парой городов может быть более одного авиарейса.

Выходные данные

В первую строку выходного файла выведите количество рейсов в новом плане. Далее выведите авиарейсы в формате, аналогичном формату входных данных. Пары разделяйте пробелами или переводами строк. Пары выводите в любом порядке. Если существует несколько решений, выведите любое.

Примечание

Тесты при \(N \le 20\), \(M \le 40\) оцениваются в 40 баллов и только при прохождении всех тестов группы.

Остальные тесты оцениваются независимо, но только при прохождении всех тестов первой группы.

Примеры

Входные данные

4 5
1 2 2 3 2 1 3 2 2 4

Выходные данные

4
1 3 3 2 2 1 2 4