I recently (almost a week ago) gave Google's Online Challenge. There was an interesting problem in Graph Theory stated as follows:-↵
↵
You are given an undirected weighted graph of n vertices and m edges. There are q queries where each query consists of a source, a destination and a weight w. For each query print ‘1’ if there exists a path from source to destination where each edge in the path has a width less than or equal to w.↵
↵
Constraints:-↵
↵
n,m,q<=10^5↵
↵
The constraints were particularly interesting. For a beginner like me, I couldn't think of anything but a brute force solution of BFS with a restriction that the edge weight should be less than w. Clearly, this O(V+E) for each query and quickly goes into a TLE once number of queries becomes large enough. So, how do we solve this problem?↵
Even precomputing looks difficult because each query had a different value of weight w. ↵
So, how do we solve it? I have a feeling from the constraints some kind of log factor must come into picture but I am unable to determine what would be helpful. ↵
↵
Any clues, algorithms or ideas will greatly helpful.↵
Thanks in advance.
↵
You are given an undirected weighted graph of n vertices and m edges. There are q queries where each query consists of a source, a destination and a weight w. For each query print ‘1’ if there exists a path from source to destination where each edge in the path has a width less than or equal to w.↵
↵
Constraints:-↵
↵
n,m,q<=10^5↵
↵
The constraints were particularly interesting. For a beginner like me, I couldn't think of anything but a brute force solution of BFS with a restriction that the edge weight should be less than w. Clearly, this O(V+E) for each query and quickly goes into a TLE once number of queries becomes large enough. So, how do we solve this problem?↵
Even precomputing looks difficult because each query had a different value of weight w. ↵
So, how do we solve it? I have a feeling from the constraints some kind of log factor must come into picture but I am unable to determine what would be helpful. ↵
↵
Any clues, algorithms or ideas will greatly helpful.↵
Thanks in advance.
