타임머신
골드 IV의견: 0
\(N\)개의 도시와, 한 도시에서 다른 도시로 이동하는 버스 \(M\)개가 있다. 버스의 소요 시간 \(C\)는 음수일 수도 있다 — 타임머신으로 시간을 거슬러 가는 경우다.
\(1\)번 도시에서 출발하여 나머지 도시로 가는 가장 빠른 시간을 구하여라. 시간을 무한히 거슬러 갈 수 있는 경우(음수 사이클)에는 \(-1\)만 출력한다.
\(2 \le N \le 500\), \(0 \le M \le 6\,000\), \(-10\,000 \le C \le 10\,000\).
첫째 줄에 \(N\)과 \(M\)이 주어진다. 다음 \(M\)개의 줄에 버스 정보 \(A\ B\ C\)가 주어진다 — \(A\)에서 \(B\)로 가는 데 \(C\)의 시간이 걸린다.
음수 사이클로 시간을 무한히 거슬러 갈 수 있으면 첫째 줄에 \(-1\)만 출력한다. 그렇지 않으면 \(N-1\)개의 줄에 걸쳐 \(2\)번부터 \(N\)번 도시까지 가는 가장 빠른 시간을 출력한다. 도달할 수 없으면 해당 줄에 \(-1\)을 출력한다.
3 3
1 2 4
1 3 3
2 3 -4
4
0
\(1 \to 2\)는 \(4\), \(1 \to 2 \to 3\)은 \(0\)이다.
3 2
1 2 4
1 2 3
3
-1
도시 \(3\)으로는 갈 수 없으므로 \(-1\)을 출력한다.
골드 IIIriseoj 작성
출처 Original
평가 및 의견
타임머신
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
타임머신