Đích gần nhất trong danh sách

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

Từ vị trí s, đội kỹ thuật có danh sách k trạm dịch vụ có thể tiếp nhận sự cố. Cần biết trạm nào gần nhất theo chi phí đường đi; nếu hòa, chọn mã nhỏ hơn.

Yêu cầu

In mã trạm được chọn và khoảng cách nhỏ nhất. Nếu không trạm nào tới được, in -1.

Input

Dòng đầu n, m, s, k; dòng tiếp theo k mã trạm; sau đó m cạnh có hướng u, v, w.

Output

In 'station distance' hoặc -1.

Ràng buộc

• 1 <= n <= 2*10^5
• 0 <= m <= 3*10^5
• 1 <= k <= n
• 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 6 1 2
4 5
1 2 2
2 4 3
1 3 1
3 5 4
2 5 10
3 4 10

Output

4 5

Giải thích. Sau khi có dist[], chọn trạm có cặp (distance, id) nhỏ nhất.

Ví dụ 2

Input

3 1 1 1
3
1 2 5

Output

-1

Giải thích. Sau khi có dist[], chọn trạm có cặp (distance, id) nhỏ nhất.

Thông tin bài tập

Nguồn: FULLHOUSE DEV – Self-generated.