2. LQDOJ Cup 2024 - Round #7 - Taxi tiết kiệm
Cho một thành phố gồm \(n\) địa điểm được đánh số từ \(1\) đến \(n\) và \(m\) con đường nối giữa các địa điểm sao cho luôn tồn tại ít nhất một đường đi giữa hai địa điểm bất kỳ. Có \(k\) vị khách mời đang đứng tại các địa điểm khác nhau, lần lượt là \(a_{1}, a_{2}, \ldots, a_{k}\), và tất cả họ đều cần di chuyển đến một địa điểm chung là \(T\) để tham dự một hội nghị quan trọng. Mỗi con đường đi giữa hai địa điểm \(u\) và \(v\) có một trọng số \(w\) biểu thị chi phí di chuyển bằng taxi giữa hai địa điểm này.
Các vị khách khi đi taxi có thể lựa chọn đi riêng lẻ hoặc kết hợp thành nhóm nếu họ gặp nhau tại cùng một điểm. Trong trường hợp đi chung, chi phí di chuyển sẽ được chia đều cho số vị khách cùng đi trong nhóm.
Hãy đưa ra phương án di chuyển sao cho tổng chi phí di chuyển của \(k\) người cộng lại là bé nhất có thể.
Input
- Dòng đầu tiên chứa bốn số nguyên dương \(n, m, k\) và \(T\) \((1 \leq n, m \leq 10^{4}, 1 \leq k \leq 8, 1 \leq T \leq n)\) lần lượt thể hiện số địa điểm của thành phố, số con đường của thành phố, số lượng khách mời và địa điểm tổ chức cuộc hội nghị.
- Dòng thứ hai chứa \(k\) số nguyên dương \(a_{1}, a_{2}, \ldots, a_{k}\) \((1 \leq a_{i} \leq n)\) thể hiện vị trí ban đầu của các vị khách mời.
- \(m\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(u, v\) và \(w\) \((1 \leq u, v \leq n, u \neq v, 1 \leq w \leq 10^{9})\) thể hiện rằng có một con đường hai chiều kết nối giữa địa điểm thứ \(u\) và địa điểm thứ \(v\) với giá đi taxi là \(w\).
Output
- Dòng đầu tiên chứa một số nguyên \(e\) thể hiện tổng chi phí tối thiểu trong phương án của bạn.
- Dòng thứ hai chứa một số nguyên không âm \(X\) thể hiện số lần thuê taxi trong phương án của bạn.
- \(X\) dòng tiếp theo, mỗi dòng chứa một xâu nhị phân độ dài \(k\), một số nguyên \(u\) và một số nguyên \(v\) thể hiện chuyến taxi đi từ \(u\) tới \(v\) với những vị khách đi trên chuyến taxi này được thể hiện bằng giá trị $
1$ trên xâu nhị phân.
Cách tính điểm
- Bạn sẽ nhận được \(100\%\) số điểm của test khi tổng chi phí nhỏ nhất là chính xác và phương án truy vết là một trong bất kỳ các phương án hợp lệ.
- Bạn sẽ nhận được \(0\%\) số điểm của test khi tổng chi phí nhỏ nhất sai, hoặc bạn đưa ra output sai định dạng, hoặc output của bạn chứa ký tự lạ.
- Trả lời đúng chi phí tối ưu mà truy vết sai sẽ nhận được \(40\%\) số điểm của test đó.
Scoring
- Subtask \(1\) (\(21\%\) số điểm): \(k = 1\).
- Subtask \(2\) (\(19\%\) số điểm): \(k = 2\).
- Subtask \(3\) (\(17\%\) số điểm): \(k \leq 6\).
- Subtask \(4\) (\(15\%\) số điểm): \(n, m \leq 500\).
- Subtask \(5\) (\(15\%\) số điểm): \(m < n\).
- Subtask \(6\) (\(13\%\) số điểm): Không có ràng buộc gì thêm.
Example
Test 1
Input
5 5 2 2
5 2
1 2 2
5 4 9
1 3 2
5 3 5
4 2 19Output
9
3
10 5 3
10 3 1
10 1 2Note
Trong ví dụ này có \(2\) vị khách đứng ở \(5, 2\) cần di chuyển tới địa điểm \(2\). Vì vị khách ở vị trí \(2\) đã ở tại địa điểm cuộc họp nên vị khách này không cần di chuyển còn vị khách đứng ở vị trí \(5\) sẽ chọn lộ trình ngắn nhất để đi tới địa điểm \(2\) là \(5 \rightarrow 3 \rightarrow 1 \rightarrow 2\). Lộ trình này tốn số tiền taxi là \(5 + 2 + 2 = 9\).
Test 2
Input
10 11 3 9
1 10 7
2 10 15
5 2 35
3 7 28
1 9 27
10 9 48
4 10 14
9 8 29
5 8 48
9 6 11
8 7 13
10 1 6Output
75
4
010 10 1
001 7 8
110 1 9
001 8 9Note
Trong ví dụ này lộ trình tối ưu nhất sẽ là:
Vị khách thứ hai đi taxi từ vị trí \(10\) đến vị trí \(1\), sau đó vị khách thứ hai và thứ nhất cùng nhau đi taxi đến vị trí cuộc họp (vị trí \(9\)) tốn \(6 + 27 = 33\).
Còn vị khách thứ ba sẽ bắt taxi đi từ \(7 \rightarrow 8 \rightarrow 9\) tốn \(13 + 29 = 42\).
Tổng cộng tốn \(33 + 42 = 75\) chi phí đi taxi. Có thể chứng minh đây là chi phí bé nhất.
