Описание

Ограничение по времени: 500 ms
Ограничение по памяти: 32 Mb

Ответы на вопросы

Задача: Negcycle. Отрицательный цикл

Negcycle. Отрицательный цикл

Дан взвешенный ориентированный граф. Требуется определить, содержит ли он цикл отрицательного веса. Гарантируется, что все вершины графа достижимы из первой.

Формат входных данных

Первая строка входного файла содержит два натуральных числа n и m — количество вершин и ребер графа соответственно (n ≤ 1 111, m ≤ 11 111).
Следующие m строк содержат описание ребер по одному на строке. Ребро номер i описывается тремя числами bi, ei и wi — номера концов ребра и его вес соответственно (1 ≤ biei ≤ n, −100 000 ≤ wi ≤ 100 000). Обратите внимание, что в графе могут быть кратные ребра и петли.

Формат выходных данных

Первая строка выходного файла должна содержать yes, если граф содержит цикл отрицательного веса и no — в противном случае.
Примеры
входные данные
4 4
2 1 -4
1 2 1
3 4 2
2 3 3
выходные данные
yes
 
входные данные
4 6
2 1 4
1 2 1
3 4 2
2 3 3
1 1 2
1 2 2
выходные данные
no


Прикрепите файл с исходным кодом программы:
     
или введите исходный код на языке:


Правила оформления программ и список ошибок при автоматической проверке задач
           

Ваш ответ:

Загруженные файлы:


Нет

Примечание учителя: