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.