취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 13317번 문제인 한 번 남았다이다.
문제는 아래 링크를 확인하자.

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

지문에 적혀있듯 주어진 코드는 "음수 사이클이 없음에도 (음수 사이클이) 있다고 판별하기 때문에 틀"린 코드이다.

Bellman-Ford의 반복문을 N-1바퀴 돌아야 최단거리를 구할 수 있는 케이스는 무엇일까?

반복문을 한 바퀴 돌면 (최단거리에 해당하는 경로의 탐색이 끝나지 않은 이상) 적어도 하나의 새로운 노드의 거리가 갱신이 되게 되므로, N-1번 최단거리가 갱신되기 위해서는 모든 노드를 전부 거쳐가는 경로가 최단거리가 되어야 한다.

그런 경우중 가장 단순한 경우는 N-1개의 노드가 일렬로 이어진 일자트리 모양 그래프이므로 글쓴이는 이러한 모양의 그래프를 답으로 구하였다.

이를 주어진 출력형식에 맞춰 만들어 출력해주자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cout << 50 << ' ' << 49 << '\n';
	for (int i = 49; i > 0; i--) cout << i << ' ' << i + 1 << ' ' << -1 << '\n';
}