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 passes without a TLE?
Here is my code,
#include <iostream>
#include <deque>
#include <map>
#include <vector>
#include <utility>
#include <algorithm>
#include <climits>
#define NIL -1
typedef struct distances{
int index;
int dist;
}distances;
bool compareheap(distances a,distances b){
return a.dist < b.dist;
}
int findIndex(std::deque<distances>heap,int vertex){
int size = heap.size();
int index = NIL;
for(int i=0;i<size;i++){
if(heap[i].index == vertex){
index = i;
}
}
return index;
}
bool comparePt(std::pair<int,int> a,std::pair<int,int>b){
return a.second > b.second;
}
int dijkstra(std::vector<std::vector<int> >graph,int vertex,int size){
std::map<int,int>map;
map.insert(std::pair<int,int>(vertex,0));
std::deque<distances>heap;
for(int i=0;i<size;i++){
if(i == vertex){
continue;
}
if(graph[vertex][i] != NIL){
distances a;
a.index = i;
a.dist = graph[vertex][i];
heap.push_back(a);
}else{
distances a;
a.index = i;
a.dist = INT_MAX;
heap.push_back(a);
}
}
//std::cout << "got here" << std::endl;
while(!heap.empty()){
sort(heap.begin(),heap.end(),compareheap);
distances top = heap.front();
heap.pop_front();
int ind = top.index;
int distance = top.dist;
//std::cout << ind << ' ' << distance << std::endl;
map.insert(std::pair<int,int>(ind,distance));
//std::cout << "got here" << std::endl;
for(int i=0;i<size;i++){
//std::cout << i << std::endl;
//std::cout << ind << ' ' << i << std::endl;
if(graph[ind][i] != NIL){
//std::cout << "got here" << std::endl;
int index = findIndex(heap,i);
if(index == NIL){
continue;
}
//std::cout << "got here" << std::endl;
int d = graph[ind][i]+distance;
if(d < heap[index].dist){
heap[index].dist = d;
}
}
}
//std::cout << "got here" << std::endl;
}
std::vector<std::pair<int,int> >v;
std::copy(map.begin(),map.end(),back_inserter(v));
sort(v.begin(),v.end(),comparePt);
return v[0].second;
}
int main(){
int city,connections;
std::cin >> city >> connections;
std::vector<std::vector<int> >graph(city,std::vector<int>(city,NIL));//Adjacency matrix for storing the graph
for(int i=0;i<connections;i++){
int a , b;
std::cin >> a >> b;
a--;b--;
std::cin >> graph[a][b];
graph[b][a] = graph[a][b];
}
int max = 0;
for(int i=0;i<city;i++){
int highest = dijkstra(graph,i,city);//do dijkstra for each and every vertex
if(highest > max){
max = highest;
}
}
std::cout << max << std::endl;
return 0;
}
