The programming club at Don Mills has been booming lately, and so Griffy has decided to install a system to figure out the path that students should take to reach the club room (which is not necessarily held in the same room every time). He hopes that this act of kindness will weaken Timothy Li's defenses so he will be able to beat him up at tic-tac-toe. There are rooms numbered from to , and one-way hallways that connect two locations. Each hallway takes minutes to traverse. Given queries in the form
a b, where is not equal to , find the least amount of time needed to go from room to room . If it is not possible to get from to , output
Not enough hallways!.
First line, three integers , , .
Next lines, two integers
a b on each line describing a one-way hallway from to .
Line , one integer .
Lines , two integers
a b the query rooms.
One line for each query, the shortest amount of time taken to go from room to room .
7 6 8 2 3 5 7 1 7 3 4 4 3 1 2 3 1 7 4 2 1 4
8 Not enough hallways! 24
Can someone please take a look at my code. I'm getting TLE on the last test case and I'm not sure why. Edit - NVM I found my problem: for anyone else attempting this problem, note that M is far less than N^2. Therefore an adjacency list is more efficient than an adjacency matrix.
I don't see why I'm getting WA. Help?
edit: I was invoking undefined behaviour. Thanks.
There's something really sketchy when you call g() while reading in the edges (perhaps undefined behaviour). Change it to how you would normally read in edges and it ACs.
What's slowing down my code?
I used BFS to find all connected rooms and stored each room and time in separate answer arrays. I used the fastest input method and managed to AC all the test cases but the last one. What can I make faster?
Each of your queries takes linear time to answer (not much faster than BFS itself). Try to find a way to store your answers so you can answer queries in constant time.
I did as you suggested and stored the answers in a single, larger array within which the value of the second query room was the index for the time it took to get there, but I still TLE'd the last case.
Try modifying your BFS function to use only 1 for loop instead of 2
You've already solved this in python, correct? Are there any significant differences in our approaches to the question?
Remember to try submitting a few times, as the grading speed is inconsistent. It is totally possible to TLE one time and then AC with the exact same code another.
Our approaches are mostly the same. The main difference is the way we programmed the BFS function. Honestly, I'm not sure why your code is TLEing.
I don't think the double for loop really has much effect on the overall runtime because the first for loop just makes sure that all of the rooms at that breadth are checked at the same time. It runs through all the items in the queue just as it would without the for loop.
I think you're over thinking this, you have so many variables that you just don't need.
It won't affect the overall time complexity, but might help with constant optimization
TLE'd again. I think the issue may lie in how I'm currently running the BFS from each source node, but idk anymore.
Use a source node, pop in the connected nodes, sift through the connected to that connected (friends of friends) and say the distance from the source to the friend of friend is just 1 more.
Given that the time limit is ten seconds, try something like floyd?
Floyd takes time and might TLE in Python. Doing BFS from every room and storing the answers in a 2D array should be sufficient enough.
Floyd's will not TLE in C++, for me the longest case took just under 2 seconds. The BFS solution is clearly better though, and I will try it now!
What kind of hallways are unidirectional?
Sketchy DMCI hallways.
"gates of truth"