Vận chuyển

View as PDF

Submit solution

Points: 100.00
Time limit: 1.0s
Memory limit: 1G
Input: stdin
Output: stdout

Authors:
Problem type
Allowed languages
C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, Text

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 uivi với nhau và có giới hạn tải trọng là li. 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à wi, xuất phát từ chi nhánh si và muốn dừng ở chi nhánh ti. 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 ui,vi,li(1ui,vin,li109), thể hiện rằng con đường i nối đỉnh ui với vi và có giới hạn tải trọng là li.
  • q dòng tiếp theo, dòng thứ i gồm ba số nguyên dương si,vi,wi(1si,tin,wi109) 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 ra "NO".

Example

Sample input

Copy
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

Copy
YES
YES
YES
NO

Scoring

  • Subtask 1 (30% số điểm): n,m,q,wi,li100
  • Subtask 2 (20% số điểm): n,q2105,m=n1,ui<vi=i+1(1im),si=1(1iq)</li>
  • Subtask 3 (20% số điểm): n,q2105,m=n1,ui<vi=i+1(1im)</li>
  • Subtask 4 (30% số điểm): n,m,q2105

Note

  • Chuyến xe thứ nhất có thể đi chặng đường 123.
  • Chuyến xe thứ hai có thể đi chặng đường 234.
  • Chuyến xe thứ ba không cần di chuyển thì vẫn đã tới chi nhánh 1.

Comments

Please read the guidelines before commenting.


There are no comments at the moment.