6198 : SPFA
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
시작 노드 S에서 모든 노드로 가는 최단 거리를 구하시오. 단, 음수 사이클이 존재하는 경우 -1을 출력합니다.
입력 설명
첫째 줄에 노드의 개수 N, 간선의 개수 E (1 ≤ N, E ≤ 100,000), 시작 노드 S가 주어집니다.
둘째 줄부터 E개의 줄에 간선 정보 u, v, w가 주어집니다.
둘째 줄부터 E개의 줄에 간선 정보 u, v, w가 주어집니다.
출력 설명
시작 노드 S에서 모든 노드로 가는 최단 거리를 공백으로 구분해 출력하며, 음수 사이클 감지 시 -1을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4 4 1
1 2 2
2 3 3
3 4 -6
4 2 2
출력 예시
COPY
복사되었습니다!
복사되었습니다!
-1