Điện toán đám mây (aws.*)

Hiện nay, điện toán đám mây đang trở nên phổ biến và phát triển vượt bậc, trở thành xu thế công nghệ hàng đầu mà các tổ chức, doanh nghiệp hướng tới. Một trong những nhà cung cấp tiên phong trong dịch vụ điện toán đám mây là Amazon Web Service (AWS). AWS đang dẫn đầu về doanh thu và sự phổ biến với hơn 50% doanh thu về dịch vụ này trên.

Để có thể tạo ra những service phục vụ hàng triệu người dùng trên toàn cầu, AWS xây dựng được một hạ tầng trên toàn thế giới. Theo thống kê, hầu hết các nước phát triển trên toàn cầu đều có trung tâm dữ liệu do AWS xây dựng, giúp cho người sử dụng có thể truy cập dễ dàng hơn. Hơn nữa, trên mỗi quốc gia không chỉ có một mà còn có nhiều trung tâm dữ liệu khác để phòng trường hợp một trung tâm dữ liệu bị hỏng không thể sử dụng được.

Hiện tại, AWS có \(N\) trung tâm dữ liệu, mỗi trung tâm đặt ở một địa điểm khác nhau. Đặc biệt, có một vài trung tâm dữ liệu được đặt rất gần nhau tạo thành một cụm máy. Cụ thể, trong N trung tâm dữ liệu này có G cụm máy, mỗi cụm gồm một số trung tâm dữ liệu, các trung tâm dữ liệu trong cùng một cụm kết nối trực tiếp với nhau và có cùng độ trễ là \(cost\). Hơn nữa, một trung tâm dữ liệu có thể thuộc nhiều cụm máy.

Để các trung tâm dữ liệu có thể kết nối đến nhau, AWS thêm \(M\) đường truyền, mỗi đường nối trực tiếp 2 trung tâm dữ liệu \(u\) và \(v\) có độ trễ là \(w\).

Trong \(N\) trung tâm dữ liệu, có đúng \(S\) trung tâm được gọi là server chứa các dịch vụ cho người dùng. Các trung tâm còn lại muốn được cung cấp các dịch vụ đó phải kết nối với một trong số S server trên. Trung tâm \(a\) có thể kết nối với trung tâm \(b\) nếu tồn tại đường đi từ \(a\) đến \(b\) trên mạng lưới đó, với độ trễ là tổng độ trễ các đường truyền phải đi qua.

AWS cần trả lời \(Q\) câu hỏi có dạng sau: trung tâm dữ liệu \(X\) muốn được cung cấp các dịch vụ thì độ trễ nhỏ nhất khi kết nối vào một trong các server là bao nhiêu?

Yêu cầu: Em hãy viết chương trình trả lời \(Q\) câu hỏi trên.

Dữ liệu vào:

- Dòng đầu tiên gồm 4 số nguyên \(N,\ S,\ G,\ M\ (1\ \leq \ N,\ M\ \leq \ 10^{5};\ S,\ G\ \leq \ N)\) lần lượt là số trung tâm dữ liệu, số server, số cụm máy và số đường dây mạng trên mạng lưới đó.

- Dòng thứ hai gồm \(S\) số là các trung tâm máy tính server trong số \(N\) trung tâm.

- G dòng tiếp theo, mỗi dòng có cấu trúc như sau:

+ Số đầu tiên là \(num\ (1\ \leq \ num\ \leq \ N)\), biểu thị cho số lượng các trung tâm máy tính trong cụm máy đó.

+ \(num\) số tiếp theo là chỉ số của các trung tâm dữ liệu trong cụm đó. Không có 2 trung tâm dữ liệu nào trùng nhau.

+ Cuối cùng là \(cost\ (1\ \leq \ cost\ \leq \ 10^{9})\), độ trễ để kết nối giữa 2 trung tâm bất kỳ trong cụm máy đó.

Tổng số trung tâm dữ liệu trong G cụm không quá 10⁵.

- \(M\) dòng tiếp theo, mỗi dòng gồm 3 số u, v, w là một đường dây mạng 2 chiều nối giữa trung tâm \(u\) và \(v\), với độ trễ \(w\ (1\ \leq \ w\ \leq \ 10^{9})\).

- Dòng tiếp theo chứa 1 số nguyên \(Q\ (1\ \leq \ Q\ \leq \ 10^{5})\), số lượng truy vấn.

- Q dòng cuối, mỗi dòng gồm 1 số là trung tâm dữ liệu \(X\ (1\ \leq \ X\ \leq \ 10^{5})\)

Kết quả: Ghi \(Q\) dòng, mỗi dòng một số nguyên là độ trễ nhỏ nhất cho \(Q\) câu hỏi tương ứng trong tệp dữ liệu vào.

Ví dụ:

Input	Output	Giải thích ví dụ
7 1 2 2 1 3 1 2 3 2 4 4 5 6 7 3 3 4 4 1 5 10 1 5	9	- Tổng độ trễ nhỏ nhất từ 5 đến 1 là 9

Ràng buộc:

+ Có 10% số test ứng với 10% số điểm có \(S = 1,\ G = 0\).

+ 20% số test ứng với 20% số điểm có \(S\ = \ 1\), tổng số máy trong \(G\) cụm không quá 10⁵.

+ 10% số test ứng với 10% số điểm có \(G = 0\).

+ 20% số test ứng với 20% số điểm có tổng số máy trong G cụm không quá 10³.

+ 40% số test ứng với 40% số điểm không có ràng buộc gì thêm.