BULMART

Đề: http://codeforces.com/contest/730/problem/C

Tạm dịch:

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ố c_i, k_i, p_i trong đó c_i là thành phố mà cửa hàng được đặt, k_i là số lượng bánh có trong cửa hàng và p_i 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ố g_i, r_i và a_i trong đó g_i  cho biết thành phố mà người thứ i đang ở, r_i là số lượng bánh người thứ i cần và a_i 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 r_i 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ố c_i, k_i, p_i

+ Dòng tiếp theo ghi số nguyên q

+ q dòng tiếp theo mỗi dòng ghi 3 số g_i, r_i và a_i

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ộ g_i, r_i và a_i

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

Solution:
Với mỗi truy vấn g_i, r_i và a_i , 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 g_i mua được r_i chiếc bánh với số tiền anh ta đang có là a_i

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(g_i, r_i, a_i, mid) then

            Begin

                        rest¬mid; //rest là kết quả

                        R¬mid-1;

            End else L¬mid+1;

End;

Trong đó hàm check(g_i, r_i, a_i, mid)  trả về True nếu người ở đỉnh g_i có thể mua được r_i chiếc bánh  với số tiền đang có là a_i 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(g_i, r_i, a_i, 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ừ g_i đế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