Входной файл: стандартный вход Выходной файл: стандартный выход Время на тест: 1 секунда Ограничение на память: 64MB Тесты к задаче:Скачать
Коровы фермера Джона желают свободно ходить по N (1 £ N £ 200) последовательно пронумерованным от 1 до N полям фермы, даже если поля разделены лесом. Коровы выбирают систему дорог между парами полей таким образом, чтобы можно было пройти от любого поля к любому другому полю, двигаясь по дорогам. Коровы могут ходить по дорогам в любом направлении.
Для дорог коровы могут использовать только тропы диких животных. Каждую неделю они могут выбрать для использования все или некоторые тропы диких животных, о которых им известно.
Интересно, что коровы всегда обнаруживают ровно одну новую тропу диких животных в начале каждой недели. Они должны принять решение о множестве троп, которые будут использоваться в качестве системы дорог в течение текущей недели.
Коровы могут выбирать любое подмножество троп диких животных независимо от того, какие тропы выбирались на предыдущей неделе.
Коровы всегда хотят минимизировать суммарную длину дорог, которые они собираются выбрать.
Тропы диких животных не являются прямыми. Две тропы, которые соединяют одни и те же два поля, могут иметь разную длину. Более того, в случае пересечения двух троп (что возможно только вне поля), коровы не могут переходить с одной тропы на другую в точке их пересечения.
В начале каждой недели имеется информация о тропе диких животных, которую обнаружили коровы. На основании этого ваша программа должна выводить минимальную общую длину дорог, выбранных коровами на этой неделе, либо указывать, что искомая система дорог не существует.
Входные данные: стандартный вход
Первая строка входного файла содержит два целых числа, разделенных пробелом, N и W. W – количество недель, которые должна обработать программа (1 £ W £ 6000).
Для каждой недели считывайте одну строку, содержащую информацию о вновь обнаруженной тропе диких животных . Эта строка содержит три целых числа, разделенных пробелами: концевые точки тропы (номера полей) и целочисленную длину тропы (1…10000). Не бывает тропы, у которой концевые точки находятся на одном поле.
Выходные данные: стандартный выход
Сразу после того, как ваша программа узнает о вновь обнаруженной тропе диких животных, она должна вывести одну строку, содержащую минимальную общую длину дорог, которые следует выбрать, чтобы связать все поля. Если невозможно связать все поля системой дорог, используя только тропы диких животных, то следует вывести “-1”.
Ваша программа должна заканчивать работу после вывода ответа для последней недели.