Дается взвешенный неориентированный граф, проверьте, существует ли путь веса k между вершинами 1 и n.
Похоже на NP-задачу, но меня просят проверить ее менее чем за 2 секунды, K<= 10 ^ 18. Мы можем использовать каждую дорогу столько раз, сколько захотим. Был бы благодарен за любую помощь. </p>
N и M довольно малы (<= 50), поэтому я рассматриваю использование dp для путей весом до k. N, M, K - целые числа, вес ребер <10 ^ 4. График может быть не связан. Эта проблема связана с обучением codeforces, к сожалению, утверждение не на английском языке, поэтому вложение заявления не имеет смысла. </p>
В стране есть nгорода, города имеют номера от 1 до n, все дороги в обоих направлениях. Каждая дорога соединяет два города.
Мистеру Уокеру действительно нравится гулять. Движение по любой дороге в любом направлении занимает w (i) минут. Мистер Уокер не останавливается в городах, и как только он достигает одного города, он сразу же отправляется в другой
Мистер Уокер начинает с города с номером 1 и хочет достичь n-го города ровно за K минут. Вам нужно проверить, возможно ли это.
Ввод - первая строка содержит два целых числа n, m (1 ≤ n, m ≤ 50). Следующие m строк описывают дороги a (i) - начало, b (i) - конец, d (i) - время, необходимое для прохождения всей дороги (1 ≤ ai, bi ≤ n; 1 ≤ di ≤ 10 ^ 4).
Последняя строка содержит число k - время, которое мистер Уокер хотел бы, чтобы его путь прошел (1 ≤ t ≤ 10 ^ 18).
Печать Возможно, если это так, и невозможно, если мистер Уокер не будетВы не сможете добраться до n-го города ровно за k минут.