Здравствуйте, моё решение выдаёт longtime.
моё решение: http://pastebin.com/BZ0h7PWA
подскажите, почему может так долго работать. Ведь моя идея простой обход в глубину, а превышено время даже при ограничениях n и m <1000, а k=2.
Вот текст задачи.
Как известно, в Берляндии ровно две проблемы, и дороги — одна из них.
Из курса школьной географии вам должно быть знакомо, что в Берляднии ровно n городов
и m дорог с двусторонним движением. Некоторые дороги, будем честны, находятся в плачевном
состоянии.
Для поддержания качества дорог правительство объявило некоторые из них платными. Каждая
платная дорога обслуживается одной из k компаний, которая и обеспечивает своевременный ремонт
дороги (она же и взимает плату за проезд по ней).
В Берляндии не только две проблемы, но и две столицы. Они находятся на разных широтах,
поэтому одну называют Северной, а другую — Южной. Споры о том, какая столица главнее, длятся
уже много лет, но для компаний важно не кто главнее, а то, что именно между этими двумя городами
сосредоточен основной автомобильный трафик.
Берляндская антимонопольная служба заподозрила, что дороги были распределены нечестно, а
именно, что существует путь между Северной столицей и Южной, такой что какая-то из компаний
не владеет ни одной из дорог этого пути. По мнению представителей службы, это создает нездо-
ровую конкуренцию, и таких ситуаций необходимо избегать, но для начала необходимо выявить
все компании, страдающие от подобной несправедливости. Эту нелёгкую задачу антимонопольная
служба поручила вам.
Назовем компанию обделённой, если существует какой-нибудь путь между двумя столицами, на
котором нет ни одной дороги, обслуживаемой этой компанией. Выведите номера всех обделённых
компаний.
Формат входных данных
В первой строке входных данных записаны три числа n, m и k
(2 ⩽ n, k ⩽ 100 000, 1 ⩽ m ⩽ 100 000) — количество городов, дорог и компаний соответствен-
но.
Далее следуют m строк, описывающих дороги. В i-й из них записаны три целых числа ui
, vi
и ci (1 ⩽ ui
, vi ⩽ n, 0 ⩽ ci ⩽ k) — номера городов, соединенных i-й дорогой, и номер компании,
которая эту дорогу обслуживает. При этом ci = 0 означает, что дорога осталась бесплатной и не
принадлежит ни одной компании.
В последней строке записаны два числа a и b (1 ⩽ a, b ⩽ n, a ̸= b) — номера городов, являющихся
Северной и Южной столицами соответственно.
Гарантируется, что никакая дорога не соединяет город сам с собой и между каждой парой горо-
дов проходит не более одной дороги.
Формат выходных данных
В первой строке выведите количество обделённых компаний.
Во второй строке выведите номера всех обделённых компаний в порядке возрастания. |
