Elearning CodePath – CTP Online Judge

Đại Chiến Tinh Hệ

PLANETWAR

🟢 Hard #Graph #Simulation

### Bài toán
Vào năm 3024, nhân loại bắt đầu cuộc chiến chinh phục các hành tinh của người ngoài hành tinh. Phe người sở hữu H hành tinh, phe ngoài hành tinh kiểm soát A hành tinh.

Tại mỗi hành tinh của con người (i), ban đầu có n_i tàu Saber Tooth và mỗi năm sản xuất thêm m_i tàu.
Tại mỗi hành tinh của người ngoài hành tinh (j), ban đầu có s_j voi ma mút Mammoth và mỗi năm sản xuất thêm p_j con.

Commander Bradley Bennett đề ra chiến lược: Mỗi hành tinh người (i) sẽ được phân công tấn công duy nhất một hành tinh ngoài hành tinh (j). Ngược lại, mỗi hành tinh ngoài hành tinh (j) cũng chỉ bị tấn công bởi duy nhất một hành tinh người (i).

Giả sử hành tinh người (i) xuất quân vào đầu năm T. Khi đó, số tàu mang đi là n_i + T * m_i. Thời gian di chuyển từ hành tinh (i) đến hành tinh (j) là D[i][j] năm. Tàu sẽ cập bến vào đầu năm (T + D[i][j]). Tại thời điểm này, số lượng voi ma mút tại hành tinh (j) là s_j + (T + D[i][j]) * p_j.

Điều kiện chiến thắng tại một hành tinh: Số lượng tàu người không nhỏ hơn số lượng voi ma mút tại thời điểm cập bến.

Yêu cầu: Tìm thời gian tối thiểu (năm) để tất cả A hành tinh ngoài hành tinh đều bị tiêu diệt. Nếu không thể tiêu diệt hết, in ra IMPOSSIBLE.

### Định dạng Đầu vào
Dòng đầu tiên chứa hai số nguyên H và A (1 <= H, A <= 250).
Dòng thứ hai chứa H cặp số nguyên n_i, m_i (0 <= n_i, m_i <= 40000).
Dòng thứ ba chứa A cặp số nguyên s_j, p_j (0 <= s_j, p_j <= 40000).
H dòng tiếp theo, mỗi dòng chứa A số nguyên D[i][j] (0 <= D[i][j] <= 40000) là thời gian di chuyển.
Dữ liệu kết thúc bằng dòng chứa hai số 0.

### Định dạng Đầu ra
Một số nguyên duy nhất là thời gian tối thiểu tìm được hoặc IMPOSSIBLE.

### Ví dụ
Input:
2 1
2 3 0 3
2 2
2
2
0 0

Output:
6

### Subtasks
Subtask 1 (30%): H, A <= 10; Các giá trị thời gian <= 100.
Subtask 2 (70%): H, A <= 250; Các giá trị thời gian <= 40000.

✅ Đã AC: 1 / 3 submissions