Is the graph is always connected i mean can any vertex be isolated if yes what will be the answer???
Second line of the problem statement.
All cities served by Drongo Airlines can be reached from each other by some sequence of connecting flights
So yes, the graph is always connected. There is no isolated vertex.
I implemented Dijkstra’s for every pair of vertices and returned the maximum of all. However, I am getting WAs for this. My code is here: FREE_TICKETS
Can anybody please tell me what’s wrong?
dijkstra might be too slow, use bellman-ford.
You can also try using Floyd Warshall
Dijkstra is faster than bellman-ford
Pure Floyd Warshall Problem.
Using dijkstra is better than bellman ford since it is faster and there are no negative egde weights in this question. @rajarshi_basu
Does anyone know a solution which is better than O(v^3)? Is it possible to get a better solution?
A better solution is by using dijkstra on all vertices.
i.e. O(n) * O(n log n) = O(n^2 log n)