Mock CCO '18 Contest 4 Problem 4 - Time Travel

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 0.3s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

A zergling is sent on a dangerous journey - as part of a 4-pool build, the zergling has to run to the Protoss base to harass the mining probes.

On the way to the Protoss base, the zergling encounters some wormholes that teleport the zergling to a different space and time. The zergling comes up with an ingenious idea - if she can return to the Zerg main before she was born, then she could attack the Protoss base whenever she wanted to!

Can she?

Note that beforehand, the zergling can decide which vertex to build the Zerg main at.


1 \le T \le 5

1 \le N \le 500

1 \le M \le 2500

1 \le W \le 200

1 \le A_i, B_i \le N

1 \le T_i \le 10^4

Input Specification

The first line will contain an integer T, the number of test cases. T test cases follow.

Each test case starts with three space-separated integers, N, M, and W.

Each of the next M lines contains three space-separated integers, A_i, B_i, and T_i, indicating that there is a bidirectional path connecting vertices A_i and B_i that take T_i seconds to traverse.

Each of the next W lines contains three space-separated integers, A_i, B_i, and T_i, indicating that there is a one-way wormhole connecting vertices A_i to B_i that takes the zergling back T_i seconds in the past.

Output Specification

For each test case, output YES if it is possible for the zergling to travel back to the Zerg main before she was born. Output NO otherwise.

Sample Input

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

Sample Output



  • 0
    Jerry_Gu  commented on Nov. 21, 2018, 1:02 p.m.

    In the first test case in the sample input, if there is a wormhole that takes the zerg from a to b but that is also is a path, would it affect the time? So would it take 1 second or -3 seconds to go from node 3 to 1?