Chu Trình Qua Các Trạm Bay · canuc80k1517

Có $N$ trạm được đánh số từ $1$ đến $N$ . Trạm $i$ có tọa độ nguyên $(X_{i}, Y_{i}, Z_{i})$ trong không gian ba chiều.

Chi phí đi trực tiếp từ trạm $i$ đến trạm $j$ là

∣ X_{i} - X_{j} ∣ + ∣ Y_{i} - Y_{j} ∣ + max (0, Z_{j} - Z_{i}) .

Vì thành phần độ cao chỉ tính khi đi lên, chi phí có thể phụ thuộc vào hướng di chuyển.

Bạn xuất phát tại trạm $1$ , phải ghé mọi trạm ít nhất một lần, rồi quay lại trạm $1$ . Được phép ghé lại một trạm đã thăm trên đường đi. Hãy tìm tổng chi phí nhỏ nhất.

Input

Dòng đầu chứa số nguyên $N$ .
$N$ dòng tiếp theo, dòng thứ $i$ chứa ba số nguyên $X_{i}, Y_{i}, Z_{i}$ .

Output

In tổng chi phí nhỏ nhất.

Constraints

$2 \leq N \leq 17$ .
$- 1 0^{6} \leq X_{i}, Y_{i}, Z_{i} \leq 1 0^{6}$ .
Không có hai trạm trùng cả ba tọa độ.

Scoring

Subtask $1$ ( $50%$ ): $N \leq 10$ .
Subtask $2$ ( $50%$ ): Không có giới hạn bổ sung.

Example

Test 1

Input

2
0 0 0
2 -1 4

Output

Giải thích: Đi từ trạm $1$ đến trạm $2$ tốn $2 + 1 + 4 = 7$ ; chiều về tốn $2 + 1 + 0 = 3$ . Tổng chi phí là $10$ .

Ý tưởng: Hàm chi phí thỏa bất đẳng thức tam giác. Vì thế, nếu một hành trình tối ưu ghé lại một trạm trung gian, ta có thể bỏ lần ghé lặp và nối trực tiếp hai chặng kề mà không làm tăng chi phí. Do đó tồn tại một hành trình tối ưu ghé mỗi trạm đúng một lần trước khi quay về trạm 1.
Ý tưởng: Đặt dp[mask][last] là chi phí nhỏ nhất để xuất phát từ trạm 1, đã thăm đúng tập mask và đang ở last. Khởi tạo dp[1][0]=0; từ mỗi trạng thái, thử đi đến một trạm chưa thăm. Khi đã thăm hết, cộng chi phí quay từ last về trạm 1.
Ý tưởng: Chứng minh đúng. Lập luận rút gọn ở trên bảo đảm chỉ cần xét các chu trình Hamilton bắt đầu tại trạm 1. Mọi chu trình như vậy có một trạm áp chót xác định; bỏ chặng cuối tới last cho một trạng thái con mà công thức DP đã tối ưu. Ngược lại, mỗi chuyển trạng thái tạo một tiền tố hợp lệ. Vì DP xét mọi thứ tự ghé trạm và cộng đúng chặng quay về, giá trị nhỏ nhất là đáp án.
Ý tưởng: Độ phức tạp. O(N^2·2^N) thời gian và O(N·2^N) bộ nhớ.