| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
PTIT124I - Đường ngầm kỳ quặc |
Cho trước N (1 ≤ N ≤ 500) địa điểm với M đoạn đường (hai chiều) (1 ≤ M ≤ 2500) giữa chúng. Mỗi đoạn đường sẽ mất một khoảng thời gian nào đó để đi từ điểm đầu đến điển cuối. Tuy nhiên, giữa một số địa điểm có một đường ngầm một chiều kỳ quặc trong đó người đi sẽ di chuyển qua đường ngầm từ điểm đầu đến điểm cuối nhưng không tốn thời gian mà ngược lại còn quay lại một thời điểm trước đó. Giả sử có W đường ngầm kỳ quặc như vậy (1 ≤ W ≤ 200). Hãy xác định xem một người có thể đi từ một điểm nào đó đi qua một số cạnh và một số đường ngầm để quay về điểm xuất phát vào thời gian trước khi anh ta bắt đầu đi hay không.
Giả sử thời gian để đi qua một đoạn không quá 10000 giây và thời gian được quay lại khi qua đường ngầm nào đó cũng không quá 10000 giây.
Input
Dòng đầu tiên ghi số bộ test (không quá 5). Với mỗi bộ test:
Dòng 1: Ba số: N, M, và W
Dòng 2 đến M+1: Mỗi dòng ghi 3 số (S, E, T) mô tả một đoạn đường từ S đến E và mất thời gian T giây. Giữa hai địa điểm có thể có nhiều đường nối.
Dòng M+2 đến M+W+1: mỗi dòng ghi 3 số (S, E, T) mô tả một đường ngầm một chiều từ S đến E và giúp quay lại T giây.
Output
Với mỗi bộ test, ghi ra "YES" nếu có thể, ngược lại ghi ra "NO".
Example
Input:
2
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 2 1
1 2 3
2 3 4
3 1 8
Output:
NO YES
Giải thích: Ở bộ test 2, cách đi có thể là: 1->2->3->1. Có thể bắt đầu từ bất cứ đâu trong đường đi trên.
| Được gửi lên bởi: | adm |
| Ngày: | 2012-03-10 |
| Thời gian chạy: | 0.100s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
hide comments
|
2021-01-30 10:51:55
Bài này cần chú ý là cả thời gian t ban đầu người ta cho cũng có thể là âm. :)))) |
