## GFSSOC '14 Winter J5 - Pursuit of Knowledge

View as PDF

Points: 10 (partial)
Time limit: 2.0s
Memory limit: 64M

Authors:
Problem type

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!.

#### Input Specification

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.

#### Output Specification

One line for each query, the shortest amount of time taken to go from room to room .

#### Sample Input

7 6 8
2 3
5 7
1 7
3 4
4 3
1 2
3
1 7
4 2
1 4

#### Sample Output

8
Not enough hallways!
24

• commented on Aug. 19, 2020, 8:29 p.m. edit 4

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 is far less than . Therefore an adjacency list is more efficient than an adjacency matrix.

• commented on Nov. 20, 2017, 1:44 a.m. edit 2

I don't see why I'm getting WA. Help?

edit: I was invoking undefined behaviour. Thanks.

• commented on Nov. 20, 2017, 3:26 a.m.

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.

• commented on July 29, 2017, 5:29 p.m.

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?

• commented on July 29, 2017, 6:47 p.m. edited

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.

• commented on July 29, 2017, 7:26 p.m.

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.

• commented on July 29, 2017, 11:07 p.m.

Try modifying your BFS function to use only 1 for loop instead of 2

• commented on July 30, 2017, 3:13 p.m.

You've already solved this in python, correct? Are there any significant differences in our approaches to the question?

• commented on July 30, 2017, 4:42 p.m.

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.

• commented on July 30, 2017, 4:32 p.m.

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.

• commented on July 29, 2017, 11:32 p.m.

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.

• commented on July 29, 2017, 11:50 p.m. edited

I think you're over thinking this, you have so many variables that you just don't need.

• commented on July 29, 2017, 11:41 p.m.

It won't affect the overall time complexity, but might help with constant optimization

• commented on July 29, 2017, 11:51 p.m.

TLE'd again. I think the issue may lie in how I'm currently running the BFS from each source node, but idk anymore.

• commented on July 29, 2017, 11:57 p.m.

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.

• commented on July 29, 2017, 7:44 p.m. edited

Given that the time limit is two seconds, try something like floyd?

• commented on July 29, 2017, 10:46 p.m. edited

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.

• commented on July 29, 2017, 11:07 p.m. edited

Floyd's will not TLE in C++, for me the longest case took just under 0.6 seconds. The BFS solution is clearly better though, and I will try it now!

• commented on Dec. 9, 2014, 12:30 a.m.

What kind of hallways are unidirectional?

• commented on Dec. 9, 2014, 1:06 a.m. edited
• commented on Dec. 9, 2014, 12:32 a.m.

"gates of truth"