Hành trình giới hạn tải trọng
Points
28
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Đề bài
Cho đồ thị vô hướng gồm $N$ đỉnh và $M$ cạnh, cạnh thứ $i$ nối $u_i$ và $v_i$ có trọng số $w_i$. Có $Q$ truy vấn, mỗi truy vấn gồm ba số $s, t, W$: hỏi có tồn tại đường đi từ $s$ đến $t$ chỉ sử dụng các cạnh có trọng số $\le W$ hay không?
Dữ liệu vào
- Dòng đầu tiên chứa ba số nguyên $N, M, Q$ ($1 \le N, M, Q \le 10^5$).
- $M$ dòng tiếp theo, mỗi dòng chứa $u_i, v_i, w_i$ ($1 \le u_i, v_i \le N, 1 \le w_i \le 10^9$).
- $Q$ dòng tiếp theo, mỗi dòng chứa $s, t, W$ ($1 \le s, t \le N, 0 \le W \le 10^9$).
Dữ liệu ra
- Gồm $Q$ dòng, mỗi dòng in
YEShoặcNO.
Ví dụ
| Input | Output |
|---|---|
| 4 4 3 1 2 5 2 3 10 3 4 3 1 4 8 1 3 8 1 3 10 1 4 7 |
YES YES NO |
Giới hạn
- $1 \le N, M, Q \le 10^5$
Community Discussion