6195 : 벨만-포드
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
1번 노드에서 다른 모든 노드로 가는 최단 거리를 구하시오. 단, 음수 사이클이 존재하는 경우 -1을 출력합니다.
입력 설명
첫째 줄에 노드의 개수 N, 간선의 개수 E (1 ≤ N ≤ 500, 1 ≤ E ≤ 6,000)가 주어집니다.
둘째 줄부터 E개의 줄에 간선 정보 u, v, w (-10,000 ≤ w ≤ 10,000)가 주어집니다.
둘째 줄부터 E개의 줄에 간선 정보 u, v, w (-10,000 ≤ w ≤ 10,000)가 주어집니다.
출력 설명
1번 노드에서 출발하여 2번부터 N번 노드까지의 최단 거리를 각 줄에 출력합니다. 도달할 수 없는 경우 INF를 출력합니다. 만약 음수 사이클이 존재한다면 -1을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3 4
1 2 4
1 3 3
2 3 -2
3 2 1
출력 예시
COPY
복사되었습니다!
복사되었습니다!
-1