음수 가중치 최단 경로

문제 설명

음수 가중치가 있을 수 있는 그래프에서 시작점으로부터 모든 정점까지의 최단 거리를 구하세요. 음수 사이클이 있으면 감지해야 합니다.

입력 형식

첫 줄: 정점 수 N, 간선 수 M, 시작점 S

다음 M줄: 시작 도착 가중치

출력 형식

각 정점까지의 최단 거리 (음수 사이클 있으면 "NEGATIVE CYCLE")

제약 조건

• 1 ≤ N ≤ 500
• 1 ≤ M ≤ 6,000
• -10,000 ≤ 가중치 ≤ 10,000

시간 복잡도

O(VE)