Nhiều truy vấn cùng nguồn

Bối cảnh và bài toán

Một trung tâm cứu hộ cố định s nhận q yêu cầu hỏi thời gian ngắn nhất tới các điểm khác nhau. Mạng đường là vô hướng và mọi thời gian đi là không âm.

Yêu cầu

Trả lời q khoảng cách ngắn nhất từ s tới từng đích được hỏi.

Input

Dòng đầu n, m, q, s; tiếp theo m cạnh u, v, w; dòng cuối chứa q đích.

Output

In q dòng, mỗi dòng là khoảng cách hoặc -1.

Ràng buộc

• 1 <= n <= 2*10^5
• 0 <= m <= 3*10^5
• 1 <= q <= 2*10^5
• 0 <= w <= 10^9 ## Chấm điểm | Subtask | Điểm | Điều kiện | Official tests | |---|---:|---|---| | S1 | 40 | n <= 200, m <= 500 (nếu có m) | 01–08 | | S2 | 60 | Không có ràng buộc bổ sung | 09–20 |

Ví dụ 1

Input

5 5 3 1
1 2 2
2 3 2
1 4 10
3 5 1
4 5 1
3 4 5

Output

4
6
5

Giải thích. Vì mọi truy vấn chung một nguồn, ta tính dist[] một lần rồi tra cứu.

Ví dụ 2

Input

4 1 2 1
1 2 3
2 4

Output

3
-1

Giải thích. Vì mọi truy vấn chung một nguồn, ta tính dist[] một lần rồi tra cứu.

Thông tin bài tập

Nguồn: FULLHOUSE DEV – Self-generated.