INOI problem help Free Ticket

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

1 Like

Pure Floyd Warshall Problem.

Does anyone know a solution which is better than O(v^3)? Is it possible to get a better solution?

Dijkstra is faster than bellman-ford

Using dijkstra is better than bellman ford since it is faster and there are no negative egde weights in this question. @rajarshi_basu

A better solution is by using dijkstra on all vertices.
i.e. O(n) * O(n log n) = O(n^2 log n)