Finding the max cost from the minimum cost incurred on travelling

This problem is from INOI 2014 , where I have find out the maximum cost of traveling through the cities but taking the minimum possible route cost , here is an excerpt from it,

Indian National Olympiad in Informatics 2014

Nikhil’s slogan has won the contest conducted by Drongo Airlines and
he is entitled to a free ticket between any two destinations served by
the airline. All cities served by Drongo Airlines can be reached from
each other by some sequence of connecting flights. Nikhil is allowed
to take as many connecting flights as needed, but he must take the
cheapest route between his chosen destinations.

Each direct flight between two cities has a fixed price. All pairs of
cities connected by direct flights have flights in both directions and
the price is the same in either direction. The price for a sequence of
connecting flights is the sum of the prices of the direct flights
along the route.

Nikhil has information about the cost of each direct flight. He would
like to maximize the value of his prize, so he would like to choose a
pair of cities on the network for which the cost of the cheapest route
is as high as possible.

For instance, suppose the network consists of four cities {1, 2, 3,
4}, connected as shown on the diagram.

In this case, Nikhil should choose to travel between 1 and 4, where
the cheapest route has cost 19. You can check that for all other pairs
of cities, the cheapest route has a smaller cost. For instance, notice
that though the direct flight from 1 to 3 costs 24, there is a cheaper
route of cost 12 from 1 to 2 to 3.

The solution was pretty obvious to do dijkstra's in every vertex and find the maximum cost from the incurred map, but while maximum of the tutorials use a map+heap structure which is unavailable in c++ , hence I have to use a sorted vector for the same purpose.

The problem is the code , out of 20 testcases , shows TLE on 2 , so anyone have any better idea on how to tackle that heap + map approach , so that my code passe

Floyd Warshall

Actually it is not obvious that Dijkstra is the correct algorithm because you must find the shortest path for all vertices, not just one. If you use Dijkstra, it takes \$O(E*V \log V)\$ time. If the graph has many edges, that can be as much as \$O(V^3 \log V)\$ time. Floyd Warshall on the other hand, runs in \$O(V^3)\$ time, and is also much simpler to code (it is essentially 5 lines long consisting of a triple loop and a single if statement).

Dijkstra and heap

Dijkstra would probably also solve the problem in time. As you mentioned, you did not use a proper heap. You should use a std::priority_queue instead of the deque you are currently using.

Sample implementation

Here is a program that solves the problem using Floyd Warshall:

#include 
#include 
#include 

int main(){
    int city,connections;
    std::cin >> city >> connections;
    std::vector >graph(city,std::vector(city,INT_MAX));//Adjacency matrix for storing the graph
    for(int i=0;i> a >> b;
        a--;b--;
        std::cin >> graph[a][b];
        graph[b][a] = graph[a][b];
    }
    for (int i=0;i max)
                max = graph[i][j];
        }
    }
    std::cout << max << std::endl;
    return 0;
}

StackExchange Code Review Q#146468, answer score: 3