13317번 - 한 번 남았다 스페셜 저지

최단경로 알고리즘은 Dijkstra 알고리즘밖에 모르는 지구이는 어느 날 간선의 가중치가 1과 –1만 존재하는 그래프에서 음수 사이클의 존재 여부를 구하는 문제를 보게 되었다. 지구이는 Dijkstra 알고리즘밖에 몰랐고, Dijkstra 알고리즘은 음수 간선이 있을 때 동작하지 않기 때문에 “당연히” 틀렸다. 지식이 부족하다는 것을 느낀 지구이는 구글신에게 물어볼 수밖에 없었고, 꽤 유용한 Bellman­ford 알고리즘을 알게 되었다.

Bellman­ford 알고리즘으로 음수 싸이클의 존재 여부를 찾는 방법은 다음과 같다.

1. 모든 정점의 현재 최단거리 d[v]를 0으로 초기화한다.
2. 모든 간선 u­>v (길이 D)에 대하여 d[v]에 min(d[u] + D, d[v])를 대입한다. (이는 간선을 사용할 때 거리가 더 짧아지는 경우를 고려한 것이다)
3. 2번을 (정점 개수)–1번 반복한다.
4. 2번을 한 번 더 반복했을 때, 배열 d의 값 중 하나 이상 바뀐 경우 음수 사이클이 존재하는 것이다.

하지만 지구이는 Bellman­ford의 작동 원리를 정확하게 이해하지 못했고, 그 결과 Bellman­ford를 한 번 덜 돌리는 실수를 저질렀다(즉, 3번에서 (정점 개수)–2회 반복했다). 도토리는 지구이의 코드가 음수 사이클이 없음에도 있다고 판별하기 때문에 틀렸다고 주장했지만, 지구이는 채점 결과가 “맞았습니다”였기 때문에 틀린 것을 인정하지 않았다.

도토리를 도와 지구이를 정의구현하자!

지구이의 코드는 여기에 있다.

입력은 없다.

첫 번째 줄에 정점 개수 N과 간선 개수 M을 출력한다. (50 ≤ N ≤ 100, 0 ≤ M ≤ N*(N-­1))

두 번째 줄부터 M개의 줄에 시작 정점 s, 끝 정점 e, 가중치 d를 출력한다. (1 ≤ s, e ≤ N, s ≠ e, d = 1 or ­-1)

그래프에는 중복 간선이 없어야 한다.

출력 예시는 답이 아님에 주의하라.