4
\$\begingroup\$

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.

enter image description here

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;
}
\$\endgroup\$
3
\$\begingroup\$

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 <iostream>
#include <vector>
#include <climits>

int main(){
    int city,connections;
    std::cin >> city >> connections;
    std::vector<std::vector<int> >graph(city,std::vector<int>(city,INT_MAX));//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];
    }
    for (int i=0;i<city;i++)
        graph[i][i] = 0;
    for (int k=0;k<city;k++) {
        for (int i=0;i<city;i++) {
            for (int j=0;j<city;j++) {
                if (graph[i][k] != INT_MAX && graph[k][j] != INT_MAX &&
                        graph[i][k] + graph[k][j] < graph[i][j])
                    graph[i][j] = graph[i][k] + graph[k][j];
            }
        }
    }
    int max = 0;
    for (int i=0;i<city;i++) {
        for (int j=0;j<city;j++) {
            if (graph[i][j] > max)
                max = graph[i][j];
        }
    }
    std::cout << max << std::endl;
    return 0;
}
\$\endgroup\$
  • \$\begingroup\$ A priority queue of pairs? Or copy the queue into map when changing something? \$\endgroup\$ – hellozee Nov 8 '16 at 12:48
  • \$\begingroup\$ I don't even know why you have that map. Yes a priority queue of pairs. See here for an example of Dijkstra using a priority queue without a map. \$\endgroup\$ – JS1 Nov 8 '16 at 13:19
  • \$\begingroup\$ Ahh remembered why I haven't used priority queue , cause we can't traverse it \$\endgroup\$ – hellozee Nov 8 '16 at 15:09
  • \$\begingroup\$ @KuntalMajumder Why do you need to traverse it? You should have 1 priority queue and 1 array/vector of distances. There's no need to do anything to the priority queue except add new entries and pop the front. \$\endgroup\$ – JS1 Nov 8 '16 at 18:02
  • \$\begingroup\$ to get the index of the current vertex , if I can get a smaller distance for it , I have to update it in the queue \$\endgroup\$ – hellozee Nov 8 '16 at 18:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.