Calculating shortest possible route between two given nodes

Question

I recently came across this problem:

Heroes in Indian movies are capable of superhuman feats. For example, they can jump between buildings, jump onto and from running trains, catch bullets with their hands and teeth and so on. A perceptive follower of such movies would have noticed that there are limits to what even the superheroes can do. For example, if the hero could directly jump to his ultimate destination, that would reduce the action sequence to nothing and thus make the movie quite boring. So he typically labours through a series of superhuman steps to reach his ultimate destination.

In this problem, our hero has to save his wife/mother/child/dog/... held captive by the nasty villain on the top floor of a tall building in the centre of Bombay/Bangkok/Kuala Lumpur/.... Our hero is on top of a (different) building. In order to make the action "interesting" the director has decided that the hero can only jump between buildings that are "close" to each other. The director decides which pairs of buildings are close enough and which are not.

Given the list of buildings, the identity of the building where the hero begins his search, the identity of the building where the captive (wife/mother/child/dog...) is held, and the set of pairs of buildings that the hero can jump across, your aim is determine whether it is possible for the hero to reach the captive. And, if he can reach the captive he would like to do so with minimum number of jumps.

Here is an example. There are 5 buildings, numbered 1,2,...,5, the hero stands on building 1 and the captive is on building 4. The director has decided that buildings 1 and 3, 2 and 3, 1 and 2, 3 and 5 and 4 and 5 are close enough for the hero to jump across. The hero can save the captive by jumping from 1 to 3 and then from 3 to 5 and finally from 5 to 4. (Note that if i and j are close then the hero can jump from i to j as well as from j to i.). In this example, the hero could have also reached 4 by jumping from 1 to 2, 2 to 3, 3 to 5 and finally from 5 to 4. The first route uses 3 jumps while the second one uses 4 jumps. You can verify that 3 jumps is the best possible.

If the director decides that the only pairs of buildings that are close enough are 1 and 3, 1 and 2 and 4 and 5, then the hero would not be able to reach building 4 to save the captive.

That was breadth first search problem, which is easy to figure out.

#include <iostream>
#include <vector>
#include <queue>

int main (int argc, char const* argv[])
{
    int n, m;
    std::cin >> n >> m;
    std::vector<std::vector<int> >table(n,std::vector<int>(n));
    while(m--){
        int a ,b;
        std::cin >> a >> b;
        table[a-1][b-1] = 1;
        table[b-1][a-1] = 1;
    }
    int start , end;
    std::cin >> start >> end;
    start--;end--;
    std::vector<bool>visited(n);
    std::queue<int>queue_;
    visited[start] = true;
    queue_.push(start);
    std::vector<int>minDist(n);
    std::fill(minDist.begin(),minDist.end(),31000);
    minDist[start] = 0;
    while(!queue_.empty()){
        int s = queue_.front();
        queue_.pop();
        for(int i=0;i<n;i++){
            if(!visited[i] && table[s][i] == 1){
                visited[i] = true;
                minDist[i] = std::min(minDist[i],minDist[s]+1);
                queue_.push(i);
            }
        }
    }
    std::cout <<minDist[end]<< std::endl;
    return 0;
}

The code passed 9 test cases out of the 10 and got stuck at the 10th test case, which was really big. It didn't even run on my own machine.

Here is the test case of whooping 5 MBs: 10th test case in the archive

Can someone lend me some tips for optimizing the code for such a big input?

Answer 1

Input file broken

The tenth test case you linked is broken because the first line is this:

3500 641902

But there are only 641901 edges not 641902. The last line is the start/end pair. Therefore, when you run your program on this input file, you read the last line (start/end pair) as if it were an edge. Then you try to read in the start/end pair and get garbage. I fixed the file by changing 641902 to 641901. After that, your program ran fine, but it ran into a slight bug (see next section).

Bug

The problem specifies that if there is no path, the program should print 0. You program prints 31000 instead, for example on the fixed 10.in input file. You should modify your program to detect the no path case. In other words, if the minimum distance ends up 31000 (which is your "MAX" distance), print 0 instead.

All the time spent in parsing input

Your program took 4.27 seconds to solve the hardest test case. But I found that 4.21 seconds out of 4.27 seconds was spent just doing cin >> a >> b. I read on this Stackoverflow question that the way to fix this was to do this:

std::ios_base::sync_with_stdio(false);

After I added the above line of code, it reduced the run time of your program from 4.27 seconds to 0.14 seconds for the hardest test case.

This was accepted

I just submitted this program and it was accepted. It is your program with the two fixes I mentioned:

1. Print 0 if there is no path.
2. Check for faulty inputs and print 0 if the input file is broken.

Here is the program:

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

int main (int argc, char const* argv[])
{
    int n, m;
    std::cin >> n >> m;
    std::vector<std::vector<int> >table(n,std::vector<int>(n));
    while(m--){
        int a ,b;
        std::cin >> a >> b;
        table[a-1][b-1] = 1;
        table[b-1][a-1] = 1;
    }
    int start , end;
    std::cin >> start >> end;
    start--;end--;
    if (start < 0 || start >= n || end < 0 || end >= n) {
        std::cout << "0" << std::endl;
        return 0;
    }

    std::vector<bool>visited(n);
    std::queue<int>queue_;
    visited[start] = true;
    queue_.push(start);
    std::vector<int>minDist(n);
    std::fill(minDist.begin(),minDist.end(),INT_MAX);
    minDist[start] = 0;
    while(!queue_.empty()){
        int s = queue_.front();
        queue_.pop();
        for(int i=0;i<n;i++){
            if(!visited[i] && table[s][i] == 1){
                visited[i] = true;
                minDist[i] = std::min(minDist[i],minDist[s]+1);
                queue_.push(i);
            }
        }
    }
    if (minDist[end] == INT_MAX)
        std::cout << "0" << std::endl;
    else
        std::cout <<minDist[end]<< std::endl;
    return 0;
}

Answer 2

1. I think you choice of a data table is really bad. You should consider creating nodes similar to an trie.

   struct node {
       unsigned houseID;
       unsigned firstVisited = 0;
       std::vector<node*> houseLinks;
       explicit node(unsigned id) : houseID(id) {}
   };
   

   Then your initial code would look like this:

   unsigned numHouses, numLinks;
   std::cin >> numHouses >> numLinks;
   
   std::vector<std::unique_ptr<node>> houses;
   for (unsigned house = 0; house < numHouses; ++house) {
       houses.push_back(std::make_unique<node>(house));
   }
   

   I have to say, that my compiler hat home complains about make_unique. In any case this should work too houses.push_back(std::unique_ptr<node>(new node (house)));

2. Now you have to add the links between the houses

   for (unsigned link = 0; link < numLinks; ++link) {
       unsigned house1, house2;
       std::cin >> house1 >> house2;            
       houses[house1-1]->houseLinks.push_back(houses[house2-1].get());
       houses[house2-1]->houseLinks.push_back(houses[house1-1].get());
   }
   

3. Your checking part seems right, although i would suggest to group everything as it belongs:

   unsigned start, end;
   std::cin >> start >> end;
   start--;end--;
   
   std::vector<bool> visited(numHouses, false);
   visited[start] = true;
   

4. EDIT: this is no longer relevant but i dont know how to cross it out. However, i would suggest, that you keep track of your jump length via the queue. So rather than haveing a queue<node*> have a queue<std::pair<node*, size_t>> New: I would now suggest to store the first visited field in the struct itself, which simplifies the code a lot

   std::queue<node*> jumpQueue;
   jumpQueue.push(houses[start].get());
   

   Now while you are adding something to the queue you just increment the jump index.

5. Now to your breadth first search. Obviously you can ignore any occurrence of a house that was reached before, as that would lead to an at least equally large jumping series.

   size_t result = 0;
   while (!jumpQueue.empty()) {
       auto oldHouse = jumpQueue.front();
       jumpQueue.pop();
       for (auto newHouse : oldHouse->houseLinks) {
           if (!visited[newHouse->houseID]) {
               visited[newHouse->houseID] = true;
               newHouse->firstVisited = oldHouse->firstVisited+1;
               jumpQueue.push(newHouse);
           }
           if (newHouse->houseID == end) {
               result = oldHouse->firstVisited+1;
               std::queue<node*> swapQueue;
               std::swap(swapQueue, jumpQueue);
           }
       }
   }
   

   Note, that one can directly terminate the traversal of the trie by swapping the current queue with an empty one.

6. Finally now that you have the result, or 0 if you never found the villan then print result. All together you now have:

Solution

#include <iostream>
#include <memory>
#include <queue>
#include <vector>

struct node {
    unsigned houseID;
    unsigned firstVisited = 0;
    std::vector<node*> houseLinks;
    explicit node(unsigned id) : houseID(id) {}
};

int main()
{
    unsigned numHouses, numLinks;
    std::cin >> numHouses >> numLinks;

    std::vector<std::unique_ptr<node>> houses;
    for (unsigned house = 0; house < numHouses; ++house) {
        houses.push_back(std::unique_ptr<node>(new node (house)));
    }

    for (unsigned link = 0; link < numLinks; ++link) {
        unsigned house1, house2;
        std::cin >> house1 >> house2;
        houses[house1-1]->houseLinks.push_back(houses[house2-1].get());
        houses[house2-1]->houseLinks.push_back(houses[house1-1].get());
    }

    unsigned start, end;
    std::cin >> start >> end;
    start--;end--;

    std::vector<bool> visited(numHouses, false);
    visited[start] = true;

    std::queue<node*> jumpQueue;
    jumpQueue.push(houses[start].get());

    size_t result = 0;
    while (!jumpQueue.empty()) {
        auto oldHouse = jumpQueue.front();
        jumpQueue.pop();
        for (auto newHouse : oldHouse->houseLinks) {
            if (!visited[newHouse->houseID]) {
                visited[newHouse->houseID] = true;
                newHouse->firstVisited = oldHouse->firstVisited+1; 
                jumpQueue.push(newHouse);
            }
            if (newHouse->houseID == end) {
                result = oldHouse->firstVisited+1;
                std::queue<node*> swapQueue;
                std::swap(swapQueue, jumpQueue);
            }
        }
    }

    std::cout << result << "\n";
}