Tạm dịch:
Solution:
Với mỗi truy vấn gi, ri và ai , sử dụng thuật toán tìm kiếm nhị phân để xác định độ dài ngắn nhất mà người ở đỉnh gi mua được ri chiếc bánh với số tiền anh ta đang có là ai
Có N thành phố được đánh số từ 1 đến N và w cửa hàng bán bánh được đánh số từ 1 đến w, cửa hàng thứ i được mô tả bởi 3 số ci, ki, pi trong đó ci là thành phố mà cửa hàng được đặt, ki là số lượng bánh có trong cửa hàng và pi là giá của mỗi chiếc bánh.
Có q khách hàng được đánh số từ 1 đến q, khách hàng thứ i cũng được mô tả bằng 3 thông số gi, ri và ai trong đó gi cho biết thành phố mà người thứ i đang ở, ri là số lượng bánh người thứ i cần và ai là số tiền mà người thứ i có.
Yêu cầu: Hãy cho biết khoảng cách nhỏ nhất mà người thứ i cần di chuyển để mua được ri bánh. Nếu không mua được bánh thì ghi -1. Biết rằng việc mua bánh của người này không ảnh hưởng đến người khác.
Dữ liệu vào: từ tệp văn bản BULMART.INP
+ Dòng đầu tiên ghi 2 số nguyên n và m cho biết có n thành phố và m tuyến đường, mỗi tuyến đường nối 2 thành phố khác nhau
+ m dòng tiếp theo, mỗi dòng ghi 2 số u và v cho biết có 1 tuyến đường giữa hai thành phố u và v với độ dài bằng 1
+ Dòng tiếp theo ghi số nguyên w
+ w dòng tiếp theo dòng thứ i ghi 3 số ci, ki, pi
+ Dòng tiếp theo ghi số nguyên q
+ q dòng tiếp theo mỗi dòng ghi 3 số gi, ri và ai
Dữ liệu ra: ghi vào tệp BULMART.OUT gồm q dòng, mỗi dòng trả lời cho 1 bộ gi, ri và ai
Ví dụ:
BULMART.INP
|
BULMART.OUT
|
Giới hạn
|
6 4
4 2 5 4 1 2 3 2 2 4 1 2 3 2 3 6 1 2 6 2 3 7 3 1 2 4 3 8 5 2 5 6 1 10 |
2
-1 2 2 3 -1 |
+ 1≤ n, w ≤5000
+ 1≤ci≤n
+ 1≤ki, pi≤2.105
+ 1≤q≤1000
+ 1≤gi≤n
+ 1≤ri, ai≤109
|
Với mỗi truy vấn gi, ri và ai , sử dụng thuật toán tìm kiếm nhị phân để xác định độ dài ngắn nhất mà người ở đỉnh gi mua được ri chiếc bánh với số tiền anh ta đang có là ai
L ¬0; R¬N (N là số đỉnh của đồ thị)
rest¬-1;
While L≤R do
Begin
Mid¬ (L+R) div 2;
If check(gi,
ri, ai, mid) then
Begin
rest¬mid; //rest là kết quả
R¬mid-1;
End else L¬mid+1;
End;
Trong đó hàm check(gi, ri, ai,
mid) trả về True nếu người ở đỉnh
gi có thể mua được ri chiếc bánh với số tiền đang có là ai và các cửa
hàng mà người đó mua có khoảng cách không quá mid.
Để xây dựng hàm check(gi, ri, ai,
mid) cần:
Duyệt tất cả các cửa hàng bán bánh trong khoảng cách không
quá mid
để mua, tuy nhiên ta cần duyệt cửa hàng nào có giá rẻ hơn trước. Lúc này cần giải
quyết 2 vấn đề:
1. Làm thế nào để biết được khoảng cách từ gi
đến tất cả các đỉnh khác? Do đồ thị đã cho không trọng số nên ta có thể chuẩn bị
trước bằng mảng D[u,v] là độ dài đường đi ngắn nhất từ u đến v bằng cách dùng
thuật toán BFS để tìm khoảng cách ngắn nhất giữa hai đỉnh bất kỳ:
For u:=1 to n do BFS(u);
lưu khoảng cách ngắn nhất từ đỉnh u đến v
vào mảng D[u,v]
2. Làm thế nào để duyệt các cửa hàng có giá bán từ nhỏ đến lớn:
sắp xếp tăng dần theo giá trị của chiếc bánh
