https://www.acmicpc.net/problem/13317

벨만 포드의 간선완화를 구현하는데 문제가 있었지만 통과했다고 우기는 사람을 참교육하기 위해 반례를 찾는 내용이다.

간선완화는 특정 시작점으로부터 n-1번 반복해서 나머지 점까지의 최단 거리를 구하는 방법이다.
여기서 n번째부터 반복을 시작할 때 최단거리가 업데이트 된다면 이거는 음의 사이클이 발생했다는 것으로 판단할 수 있게 된다.

문제에서는 간선 완화를 할 때, n-2번만 반복해서 최단 거리가 하나 덜 구해진 상태이다.
거기서 음수 사이클 검증을 위한 간선완화를 다시 진행할 때 n-1번째 간선완화가 진행되어서 값이 업데이트 되는데, 문제 상황에서는 이거를 음의 사이클에 대한 증거로 판단해서 음의 사이클이 없지만 있다고 결론을 내린 상황이다.

그래서 모든 간선이 음수이고, 사이클이 없는 그래프를 만든다면 반례로 사용할 수 있을 것이다.

Python

n, m = 50, 49

print(n, m)

start = 1

edges = []

for i in range(m):
    a, b, c = start, start + 1, -1
    edges.append((a, b, c))
    start += 1

for e in reversed(edges):
    print(" ".join(map(str, e)))

문제의 조건이 n이 50이상 100 이하여서 n을 50으로 초기화하고 사이클이 생길 수 없게 m을 49로 선언했다.

그리고 1 -> 2, 2 -> 3 이런식으로 일렬로 연결되도록 설정하고 간선의 코스트는 -1로 주었다.