Đường đi Hamilton ngắn nhất

Buổi 33 — Bitmask DP & SOS DP
Points
25
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Submissions
Đề bài

Cho một đồ thị có hướng có trọng số gồm $N$ đỉnh đánh số từ $1$ đến $N$ và $M$ cạnh. Một đường đi Hamilton là đường đi qua tất cả $N$ đỉnh, mỗi đỉnh đúng một lần (có thể bắt đầu ở bất kỳ đỉnh nào và kết thúc ở bất kỳ đỉnh nào). Hãy tìm tổng trọng số nhỏ nhất của một đường đi Hamilton. Nếu không tồn tại đường đi Hamilton, in ra -1.

Dữ liệu vào
  • Dòng đầu chứa hai số nguyên $N$ và $M$ ($1 \le N \le 16$, $0 \le M \le N(N-1)$).
  • $M$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u, v, w$ ($1 \le u, v \le N$, $u \ne v$, $1 \le w \le 10^9$) biểu thị cạnh có hướng từ $u$ đến $v$ trọng số $w$.
Dữ liệu ra
  • In ra tổng trọng số nhỏ nhất của đường đi Hamilton, hoặc -1 nếu không tồn tại.
Ví dụ
Input Output
4 5
1 2 3
2 3 4
3 4 5
1 3 10
4 1 2
9
3 2
1 2 5
1 3 5
-1
Giới hạn
  • $1 \le N \le 16$
  • $1 \le w \le 10^9$
Draft saved