블랙홀 경보
골드 IV의견: 0
우주선이 출발지 행성(노드 \(1\))에서 \(N\)개의 행성을 탐사한다. 행성 사이에는 \(M\)개의 단방향 항로가 있고, 각 항로에는 에너지 소비량 \(w\)가 있다 (\(w < 0\)이면 에너지를 얻는 항로).
어떤 행성이 음수 사이클에 연결되어 있다면, 그 행성까지의 에너지 소비는 무한히 줄어들 수 있어 \(-\infty\)로 표시한다.
각 행성에 대해:
- 출발지에서 도달할 수 없으면 X
- 출발지에서 도달 가능한 음수 사이클의 영향을 받으면 -INF
- 그 외에는 최솟값 에너지 소비를 출력하여라.
- \(1 \le N \le 500\)
- \(0 \le M \le 5\,000\)
- \(-10^6 \le w \le 10^6\)
첫째 줄에 행성의 수 \(N\)과 항로의 수 \(M\)이 주어진다.
다음 \(M\)개의 줄에 항로 정보 \(u\), \(v\), \(w\)가 주어진다.
\(N\)개의 줄에 행성 \(1\)부터 \(N\)까지 순서대로 결과를 출력한다.
4 4
1 2 2
2 3 -5
3 2 1
1 4 3
0
-INF
-INF
3
노드 \(2\)와 \(3\) 사이에 음수 사이클(\(2+(-5)+1=-2\))이 있다. 노드 \(1\)에서 이 사이클에 도달할 수 있으므로 노드 \(2\), \(3\)은 \(-\infty\)이고, 노드 \(4\)는 직접 연결되어 \(3\)이다.
4 3
1 2 5
3 4 -3
4 3 1
0
5
X
X
\(3\to4\to3\) 사이클의 합이 \(-3+1=-2\)로 음수이지만, 노드 \(1\)에서 노드 \(3\), \(4\)에 도달할 수 없다. 노드 \(3\), \(4\)는 \(X\)이고 노드 \(2\)는 \(5\)이다.
riseoj 작성
출처 Original
평가 및 의견
블랙홀 경보
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
블랙홀 경보