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)