Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PTIT016I - ACM PTIT 2016 I - Hội trại

 

Hội khỏe Phù Đổng tổ chức vào ngày 24 tháng 3 để tiến tới tổ chức chào mừng ngày thành lập Đoàn, có n đoàn (sinh viên và khách mời) được đánh số từ 1 đến n, từ các tỉnh thành trên cả nước tập trung tổ chức hội trại giao lưu thể thao ca nhạc. Khu vực hội trại có n trại được đánh số từ 1 đến n. Đoàn thứ i đươc phân vào trại i. Sơ đồ giao thông của khu vực hội trại gồm m đoạn đường hai chiều, mỗi đoạn đường nối trực tiếp hai trại khác nhau. Sơ đồ giao thông đảm bảo là giữa hai trại bất kỳ luôn có đường đi nối chúng. Trong số các trại này có p trại khách mời (y1, y2,…, yp), các trại này cần được giữ yên tĩnh. Giữa các trại tổ chức các hoạt động giao lưu diễu hành. Hai trại u và v giao lưu bằng cách đi diễu hành từ trại u sang trại v thông qua đường đi trực tiếp nếu có hoặc đi qua một dãy các trại trung gian, ở mỗi trại tổ chức đánh trống, thổi kèn, nhảy múa, hát hò ầm ĩ. Để giữ sự yên tĩnh cho các trại khách mời nên đoàn diễu hành cần chọn đường đi giảm gây ồn nhiều nhất cho các trại khách mời.
Giả sử L(u,v)=(x1, x2,…, xk), trong đó u=x1, v=xk và có đoạn đường nối xi với xi+1 với mọi i = 1, 2, ..., k–1, là một hành trình của đoàn diễu hành từ trại u đến trại v, Ban tổ chức hội trại định nghĩa độ giảm thanh của hành trình L(u,v) là
 ,
với D(xi, yj) là độ dài đường đi ngắn nhất giữa hai trại xi và yj.
Yêu cầu: Với hai trại u và v hãy tìm hành trình có độ giảm thanh lớn nhất.
Hội khỏe Phù Đổng tổ chức vào ngày 24 tháng 3 để tiến tới tổ chức chào mừng ngày thành lập Đoàn, có n đoàn (sinh viên và khách mời) được đánh số từ 1 đến n, từ các tỉnh thành trên cả nước tập trung tổ chức hội trại giao lưu thể thao ca nhạc. Khu vực hội trại có n trại được đánh số từ 1 đến n. Đoàn thứ i đươc phân vào trại i. Sơ đồ giao thông của khu vực hội trại gồm m đoạn đường hai chiều, mỗi đoạn đường nối trực tiếp hai trại khác nhau. Sơ đồ giao thông đảm bảo là giữa hai trại bất kỳ luôn có đường đi nối chúng. Trong số các trại này có p trại khách mời (y1, y2,…, yp), các trại này cần được giữ yên tĩnh. Giữa các trại tổ chức các hoạt động giao lưu diễu hành. Hai trại u và v giao lưu bằng cách đi diễu hành từ trại u sang trại v thông qua đường đi trực tiếp nếu có hoặc đi qua một dãy các trại trung gian, ở mỗi trại tổ chức đánh trống, thổi kèn, nhảy múa, hát hò ầm ĩ. Để giữ sự yên tĩnh cho các trại khách mời nên đoàn diễu hành cần chọn đường đi giảm gây ồn nhiều nhất cho các trại khách mời.
Giả sử L(u,v)=(x1, x2,…, xk), trong đó u=x1, v=xk và có đoạn đường nối xi với xi+1 với mọi i = 1, 2, ..., k–1, là một hành trình của đoàn diễu hành từ trại u đến trại v, Ban tổ chức hội trại định nghĩa độ giảm thanh của hành trình L(u,v) là
min {D(xi, yj)} với i = 1..k và j = 1..p
với D(xi, yj) là độ dài đường đi ngắn nhất giữa hai trại xi và yj.
Yêu cầu: Với hai trại u và v hãy tìm hành trình có độ giảm thanh lớn nhất.

 

Input

Dòng đầu chứa bốn số nguyên dương n, m, p, q (n ≤ 10^5, m ≤ 2×10^5, q ≤ 10^5), trong đó n là số lượng trại, m là số lượng đoạn đường, p là số lượng trại khách mời (p ≤ n) và q là số lượng truy vấn;

Mỗi dòng trong số m dòng tiếp theo là thông tin về một đoạn đường gồm ba số nguyên dương u, v, l (u, v ≤ n; l ≤ 1000), cho biết hai trại u và v được nối trực tiếp bởi đoạn đường có độ dài l;

Dòng tiếp theo chứa p số nguyên dương là các chỉ số của các trại khách mời;

Mỗi dòng trong q dòng tiếp theo gồm hai số nguyên dương u và v đòi hỏi trả lời truy vấn: “Tìm hành trình từ trại u đến trại v có độ giảm thanh lớn nhất”.

      Hai số liên tiếp trên cùng dòng được ghi cách nhau bởi dấu cách. 

Output

Gồm q dòng: Dòng thứ i ghi một số nguyên dương là độ giảm thanh lớn nhất tìm được đối với truy vấn thứ i.

Example

Input:

6 7 2 2

1 3 2

2 3 6

2 4 1

3 4 2

3 5 4

5 4 5

4 6 3

1 6

2 5

6 3

 

Output:

3

0

 

Hình vẽ minh họa cho ví dụ:


Được gửi lên bởi:Admin
Ngày:2016-04-26
Thời gian chạy:1s-3s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO KTLN OCT PAS-GPC PAS-FPC PERL6 PERL PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

hide comments
2016-07-13 10:54:11
trong cái example output dòng 2 phải là 2 ms đúng chứ nhỉ? sao lại là 0 nhỉ
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.