[백준] 13317번 한 번 남았다

#define fastio cin.tie(0)->sync_with_stdio(0)
using namespace std;
int main(){
    fastio;
    cout<<50<<' '<<49<<'\n';
    for(int i=49; i>0; i--) cout<<i<<' '<<i+1<<' '<<-1<<'\n';
    
}

<참고>

https://measurezero.tistory.com/419

 

N: 정점 개수 (50 ≤ N ≤ 100), M: 간선 개수 (0 ≤ M ≤ N * (N-1)), M개의 간선 정보 (u, v, w)

findNegativeCycle_Wrong()가 잘못된 구현이라, 이를 이용한 논리를 깨뜨리는 반례를 찾아야 함

findNegativeCycle()은 벨만-포드 알고리즘을 올바르게 구현하여 N-1번 반복함

 

findNegativeCycle_Wrong()은 반복 횟수가 N-2라서 일부 케이스에서 오류 발생 가능.

정점 50개, 간선 49개: 1 → 2 → 3 → ... → 49 → 50

모든 간선의 가중치: -1 (음수)

위의 코드(반례)는 길이가 긴 경로를 만들면서 음수 사이클을 형성하여 findNegativeCycle_Wrong()의 오류를 유발한다.

반례에서 findNegativeCycle_Wrong()과 findNegativeCycle()의 결과가 달라서 정답 ("AC")가 된 것이다.