Because Vladimir is a vampire Vladimir has never had any pro

Because Vladimir is a vampire. Vladimir has never had any problems with bring a vampire. In fact, he is a successful doctor who always takes the\' night shift and so has made many friends among his colleagues. He has an impressive trick which lie loves to show at dinner parties: he can tell blood group by taste. Vladimir loves to travel, hut lying a vampire he must overcome three problems. He can only travel by train, because he must take his coffin with him. Fortunately lie can always travel first class because lie has made a lot of money through long term investments. He can only travel from dusk till dawn, namely, from () P.M. to (i A.M. During the day lie has must stay inside a train station. He leas to take something to rat with him. He needs one litre of blood per day, which he drinks at noon (12:00) inside his coffin. Help Vladimir to find the shortest route between two given cities, so that he can travel with the minimum amount of blood. If he takes too much with him. people ask him funny questions like, \"What are you doing with all that blood?\" Input The first line of the input will contain a single number tolling you the number of test cases. Each test case specification begins with a single number telling you how many route specifications follow. Each route specification consists of the names of two cities, the departure time from city one, and the total traveling time, with all times in hours. Remember, Vladimir cannot use routes departing earlier than 18:00 or arriving later than There will be at most 100 cities and less than 1.000 commotions. No route takes less than 1 hour or more than 21 hours, but Vladimir can use only routes within the 12 hours travel time from dusk till dawn. All city names are at most 32 characters long. \'The last line contains two city names. The first is Vladimir\'s start city; the second is Vladimir\'s destination. Output For cedi test case you should output the number of the test case followed by \"Vladimir needs # litre(s) of blood.\" or \"There is no route Vladimir can take.\"

Solution

#include <iostream>
#include <queue>
#include <map>

using namespace std;

#define MAXN 100
#define EARLIER 18
#define LATER 6
#define HOURS 24
#define NO_ROUTE (-1)

class state
{
public:
   int city, time, litres;

   bool operator<(const state &current) const
   {
       return litres > current.litres;
   }
};

class route
{
public:
   int departure;      
   int arrival;      
   int to;          
};

vector < route > edges[MAXN + 1];

int travel(int from, int to)
{
   priority_queue < state > states;

   states.push((state){from, EARLIER, 0});

   while (!states.empty())
   {
       state current = states.top();
       cout << current.city << \" \" << current.time << \" \" << current.litres << endl;
       states.pop();

       if (current.city == to)
           return current.litres;

       for (int r = 0; r < edges[current.city].size(); r++)
       {
           int used = current.litres;
           if (current.time > edges[current.city][r].departure)
               used++;

           states.push((state){edges[current.city][r].to,
                   edges[current.city][r].arrival, used});
       }
   }

   return NO_ROUTE;
}

int main(int ac, char *av[])
{
   int test, routes, cases = 1;
   int from, to;
   string start, destination;
   int departure, traveling;

   cin >> test;
   while (test--)
   {
       map < string, int > cities;

       for (int i = 0; i < MAXN + 1; i++)
           edges[i].clear();

       cin >> routes;
       for (int i = 1; i <= routes; i++)
       {
           cin >> start >> destination >> departure >> traveling;
           if (cities.find(start) == cities.end())
           {
               from = cities.size();
               cities[start] = from;
           }
           else
               from = cities[start];

           if (cities.find(destination) == cities.end())
           {
               to = cities.size();
               cities[destination] = to;
           }
           else
               to = cities[destination];

           departure += (departure <= LATER ? HOURS : 0);
           if (departure >= EARLIER
               && (departure + traveling) <= (HOURS + LATER))
               edges[from].push_back((route){departure,
                       (departure + traveling), to});
       }

       cin >> start >> destination;

       cout << \"Test Case \" << cases++ << \".\" << endl;

       if (start == destination)
       {
           cout << \"Vladimir needs 0 litre(s) of blood.\" << endl;
           continue;
       }

       if (cities.find(start) == cities.end()
           || cities.find(destination) == cities.end())
       {
           cout << \"There is no route Vladimir can take.\" << endl;
           continue;
       }

       from = cities[start];
       to = cities[destination];

       int litres = travel(from, to);

       if (litres == NO_ROUTE)
           cout << \"There is no route Vladimir can take.\" << endl;
       else
           cout << \"Vladimir needs \" << litres << \" litre(s) of blood.\" << endl;
   }

   return 0;
}

in.txt

3
3
Ulm Muenchen 17 2
Ulm Muenchen 19 12
Ulm Muenchen 5 2
Ulm Muenchen
10
Lugoj Sibiu 12 6
Lugoj Sibiu 18 6
Lugoj Sibiu 24 5
Lugoj Medias 22 8
Lugoj Medias 18 8
Lugoj Reghin 17 4
Sibiu Reghin 19 9
Sibiu Medias 20 3
Reghin Medias 20 4
Reghin Bacau 24 6
Lugoj Bacau
6
a b 18 8
b c 20 6
c a 19 8
e f 19 20
f g 22 6
g e 23 4
a h