Lịch trình bảo trì máy chủ
Points
100
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Một hệ thống gồm $N$ máy chủ được đánh số từ $1$ đến $N$. Kỹ sư cần đi qua bảo trì tất cả $N$ máy chủ, mỗi máy chủ đúng $1$ lần. Thời gian di chuyển từ máy chủ $i$ đến máy chủ $j$ là $C_{i,j}$.
Ngoài ra, có $K$ ràng buộc phụ thuộc dạng $(u, v)$, nghĩa là máy chủ $u$ phải được bảo trì trước máy chủ $v$. Kỹ sư có thể bắt đầu tại bất kỳ máy chủ nào không có điều kiện tiên quyết chưa thỏa mãn và kết thúc tại bất kỳ máy chủ nào. Hãy tìm tổng thời gian di chuyển nhỏ nhất để hoàn thành việc bảo trì, hoặc in ra -1 nếu không tồn tại lịch trình hợp lệ.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N$ và $K$ ($1 \le N \le 16$, $0 \le K \le N(N-1)$).
- $N$ dòng tiếp theo, mỗi dòng chứa $N$ số nguyên $C_{i,j}$ ($0 \le C_{i,j} \le 10^9$, $C_{i,i} = 0$).
- $K$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ ($1 \le u, v \le N$, $u \ne v$) mô tả máy chủ $u$ phải được bảo trì trước máy chủ $v$.
Kết quả
- In ra một số nguyên duy nhất là tổng thời gian di chuyển nhỏ nhất, hoặc
-1nếu không thể thực hiện.
Subtasks
- Subtask 1 (25% số điểm): $N \le 8$.
- Subtask 2 (25% số điểm): $K = 0$.
- Subtask 3 (50% số điểm): Không có ràng buộc bổ sung.
Ví dụ
| Input | Output |
|---|---|
| 3 1 0 5 10 10 0 2 3 8 0 1 3 |
7 |
Community Discussion