INOI problem help Free Ticket

general
,
1

Is the graph is always connected i mean can any vertex be isolated if yes what will be the answer???

2

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.

3

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?

4

dijkstra might be too slow, use bellman-ford.

5

You can also try using Floyd Warshall

1 Like
6

Dijkstra is faster than bellman-ford

7

Pure Floyd Warshall Problem.

8

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

9

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

10

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