Lịch trình bảo trì máy chủ

Buổi 67-68 — Mock IOI Dynamic Programming
Points
100
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions

Đề 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 -1 nế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
Draft saved