Hưởng ứng chuỗi các mục tiêu phát triển bền vững (SGDS) của Liên Hợp Quốc tại Việt Nam, Thành phố Hồ Chí Minh đã triển khai các hành động cụ thể để tiến đến Net Zero vào năm 2050, trong đó có việc triển khai mô hình du lịch bền vững kết hợp giao thông thông minh. Có n trung tâm du lịch được đánh số từ 1 đến n. Ở các trung tâm du lịch có thể có khu nghỉ dưỡng với diện tích sᵢ (m²) và phí thuê cᵢ (nghìn đồng). Nếu trung tâm du lịch nào không có khu nghỉ thì sᵢ = cᵢ = 0.
Giữa các trung tâm có m tuyến đường hai chiều, mỗi tuyến đường nối giữa hai trung tâm u và v có thời gian di chuyển là w phút. Hệ thống đảm bảo luôn có đường đi từ trung tâm này đến trung tâm khác.
Chợ Bến Thành là điểm xuất phát của hầu hết các hành trình khám phá của du khách. Có Q tour du lịch, tuỳ thuộc vào lịch trình mà mỗi tour có thể yêu cầu nơi nghỉ dưỡng có diện tích nằm trong khoảng [Lⱼ, Hⱼ] và thời gian di chuyển từ trung tâm đến địa điểm nghỉ dưỡng không vượt quá rⱼ phút.
Là một chuyên gia giàu kinh nghiệm trong lĩnh vực lữ hành, bạn hãy tư vấn cho khách hàng sao cho tìm được một địa điểm nghỉ dưỡng có chi phí thấp nhất trong số các địa điểm có cung cấp dịch vụ lưu trú ứng với mỗi Tour khách hàng đã chọn, nếu không có địa điểm nào phù hợp thì trả về giá trị -1.
| Dữ liệu vào Sao chép |
4 4 2 100 500 80 300 50 200 0 0 1 2 4 2 3 3 3 4 2 1 4 6 60 100 5 40 90 8 |
| Dữ liệu ra Sao chép |
300 200 |
| Dữ liệu vào Sao chép |
2 1 1 0 0 19 1 1 2 71 46 100 86 |
| Dữ liệu ra Sao chép |
-1 |
→ Chọn rẻ nhất trong số phù hợp: TT2 → 300
→ TT2 và TT3 đều hợp lệ → chọn rẻ nhất: TT3 → 200