2009 Canadian Computing Competition, Stage 2
Day 1, Problem 3: Beware of the Geoducks
After perfecting the art of converting water to working C++ code, Stan Velikiy is once again facing his arch-nemesis, Mario the Wabbit. At the moment, Stan is chasing Mario on a circuit and you, as the amused observer, are being asked to predict the outcome.
The circuit can be thought as of series of nodes connected by wires of specified length. Stan and Mario each start at one of the nodes and travel along the nodes in a predetermined plan. They visit the nodes according to the plan, travelling along the wires at a speed of one meter per second. Once their travel plans run out, they stay stationary at that node.
If Stan and Mario are ever in the same location, Stan will apprehend Mario. If Stan exceeds a time limit of t he gives up and goes back to converting more water into C++ code.
Unknown to either Stan or Mario, there is a series of geoducks sitting at various nodes of the circuit. Even though they look harmless, they are remnants of top-secret experiments on the Infinite Ambiguity Drive which causes whoever reaches them to disappear instantly. Once either Mario or Stan disappear, Stan can never find Mario. Note that if Stan finds Mario on a node with a geoduck, they both disappear and Stan never finds Mario.
Input
The first line contains six integers: V, the number of nodes (0 ≤ V ≤ 100); E (0 ≤ E ≤ 1000), the number of wires; S and M (1 ≤ S, M ≤ 1000), the number of nodes in the routes taken by Stan and Mario, respectively; G (0 ≤ G ≤ 100), the number of geoducks; and t (0 ≤ t ≤ 1000), the time limit.
The next E lines contain 3 integers per line, specifying two nodes that a wire connects and the length l (1 ≤ l ≤ 2000) of the wire. No wire connects a node to itself and there is at most one wire between two nodes.
The next S lines contain one integer per line, which indicate the nodes of Stan's route in the order of being visited.
The next M lines contain one integer per line, the nodes of the Mario's route in the order of being visited.
The last G lines contain one integer per line, where each line indicates the location (node) where there is a geoduck.
Output
On one line, output YES if Stan catches Mario before the time limit expires, NO otherwise.
Sample Input
3 1 2 2 1 3
1 2 6
1
2
2
1
3
Sample Output
YES
Explanation
Stan travels from node 1 to 2 while Mario moves in the other direction. There is a geoduck on node 3.
Stan catches the Mario just as time expires, and fortunately none of them ever find a geoduck.
All Submissions
Best Solutions
Point Value: 20
Time Limit: 1.00s
Memory Limit: 128M
Added: Jun 06, 2009
Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
Comments (Search)
Would Mario be caught in this situation?