Desolation of Smaug
All submissions for this problem are available.
Frodo Baggins is trying to run from the fury of Smaug. Let’s assume we represent our city by a weighted undirected connected graph(with no self-loops and multi-edges) with N nodes and N edges.
You will be given Q queries of form:
St De S Vf VS
Frodo is currently at node St and needs to reach node De. He moves with constant velocity Vf.
Smaug is currently at node S and he moves with constant velocity VS.
Print “YES”(quotes for clarity), if Frodo can reach destination without being caught by Smaug no matter what paths Smaug takes.
Else print “NO”(quotes for clarity).
Note: If Frodo reaches at destination at same time as Smaug, print “NO”.
First line contains N and Q, the number of nodes and number of queries respectively.
Each of the next N lines contain integers u v and w denoting an undirected edge between nodes numbered u and v, w being the weight of the edge.
Each of the next Q lines contain queries.
For each query print the required answer in one line.
Input: 5 2 1 2 2 2 3 3 3 4 7 4 5 5 5 1 6 1 3 5 1 2 2 4 5 2 2 Output: YES NO
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
Fetching successful submissions
If you are still having problems, see a sample solution here.