Problem ID:
transport
Points:
3 (partial)
Time limit:
1.0s
Memory limit:
1G
Input:
stdin
Output:
stdout
Authors:
Problem types
Allowed languages
C, C++, Golang, Java, Pascal, Perl, Python, Rust
Công ty TNHH Một Mình Tui có ~n~ chi nhánh. Có ~m~ con đường hai chiều nối giữa các chi nhánh, con đường ~i~ sẽ nối chi nhánh ~u_i~ và ~v_i~ với nhau và có giới hạn tải trọng là ~l_i~. Con đường ~i~ sẽ chỉ cho phép các xe đi qua nếu xe có tải trọng không vượt quá giới hạn tải trọng của con đường. Giữa hai chi nhánh bất kỳ có thể có nhiều con đường và có thể tồn tại những con đường nối từ một chi nhánh tới chính nó. Ngày hôm nay có ~q~ chuyến xe, chuyến xe ~i~ sẽ có tải trọng là ~w_i~, xuất phát từ chi nhánh ~s_i~ và muốn dừng ở chi nhánh ~t_i~. Hãy cho biết các chuyến xe này những chuyến xe nào có thể hoàn thành hành trình của mình mà không đi vượt quá tải trọng của bất kỳ con đường nào.
Input
- Dòng đầu tiên gồm ba số nguyên dương ~n,m,q~, lần lượt là số chi nhánh của công ty, số con đường và số chuyến xe
- ~m~ dòng tiếp theo, dòng thứ ~i~ gồm ba số nguyên dương ~u_i, v_i, l_i~ ~(1 \leq u_i, v_i \leq n, l_i \leq 10^9)~, thể hiện rằng con đường ~i~ nối đỉnh ~u_i~ với ~v_i~ và có giới hạn tải trọng là ~l_i~.
- ~q~ dòng tiếp theo, dòng thứ ~i~ gồm ba số nguyên dương ~s_i, v_i, w_i~ ~(1 \leq s_i, t_i \leq n, w_i \leq 10^9)~ miêu tả chuyến xe thứ ~i~.
Output
- Gồm ~q~ dòng, dòng ~i~ in
YES
nếu chuyến xe ~i~ có thể hoàn thành hành trình của nó mà không đi vượt quá tải trọng của bất kỳ con đường nào, ngược lại in raNO
.
Scoring
- Subtask 1 (~30\%~ số điểm): ~n,m,q,w_i,l_i \leq 100~;
- Subtask 2 (~20\%~ số điểm): ~n,q \leq 2 \cdot 10^5, m=n-1, u_i < v_i=i+1~ ~(1 \leq i \leq m), s_i = 1~ ~(1 \leq i \leq q)~;
- Subtask 3 (~20\%~ số điểm): ~n,q \leq 2 \cdot 10^5, m=n-1, u_i < v_i=i+1~ ~(1 \leq i \leq m)~;
- Subtask 4 (~30\%~ số điểm): ~n,m,q \leq 2 \cdot 10^5~.
Sample Input
4 6 4
1 2 2
2 3 3
3 4 3
4 1 2
1 3 1
1 1 1
1 3 2
2 4 3
1 1 5
3 4 5
Sample Output
YES
YES
YES
NO
Note
- Chuyến xe thứ nhất có thể đi chặng đường ~1\rightarrow 2\rightarrow 3~.
- Chuyến xe thứ hai có thể đi chặng đường ~2 \rightarrow 3\rightarrow 4~.
- Chuyến xe thứ ba không cần di chuyển thì vẫn đã tới chi nhánh ~1~.
Comments