Đường đi Hamilton ngắn nhất
Points
25
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Đề 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
-1nế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$
Community Discussion