수면 시간 조건
골드 III의견: 0
수면 연구소에서 \(N\)명의 참가자 \(x_1, x_2, \ldots, x_N\)에 대한 수면 시간 조건 \(M\)개를 세웠다. 각 조건은 다음 형태이다:
$$ x_j - x_i \le c $$
(두 참가자의 수면 시간 차이가 \(c\)를 넘어서는 안 된다.)
모든 조건을 만족하는 정수 배정이 존재하면 합이 최소인 배정을 출력하고, 불가능하면 IMPOSSIBLE을 출력한다.
합이 최소인 배정은 차분 제약 시스템의 최단 거리 해임이 알려져 있다.
- \(1 \le N \le 500\)
- \(0 \le M \le 5\,000\)
- \(-10^6 \le c \le 10^6\)
첫째 줄에 참가자 수 \(N\)과 조건 수 \(M\)이 주어진다.
다음 \(M\)개의 줄에 조건 \(i\), \(j\), \(c\)가 주어진다. 이는 \(x_j - x_i \le c\)를 뜻한다.
가능하면 한 줄에 \(x_1, x_2, \ldots, x_N\)을 공백으로 구분해 출력한다. 불가능하면 IMPOSSIBLE을 출력한다.
3 3
1 2 3
1 3 5
2 3 1
0 0 0
\(x_1 = 0, x_2 = 0, x_3 = 1\)으로 설정하면 모든 조건 \(0 \le 3\), \(1 \le 5\), \(1 \le 1\)을 만족한다. 벨만-포드 최단 거리로 구한 최솟값 배정이다.
2 2
1 2 2
2 1 -3
IMPOSSIBLE
\(x_2 - x_1 \le 2\)이고 \(x_1 - x_2 \le -3\)(즉 \(x_2 - x_1 \ge 3\))은 동시에 성립할 수 없으므로 불가능하다.
riseoj 작성
출처 Original
평가 및 의견
수면 시간 조건
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
수면 시간 조건