fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <map>
  5. #include <string>
  6. #include <climits>
  7. #include <sstream>
  8. #include <algorithm>
  9.  
  10. using namespace std;
  11.  
  12. // Helper function to parse time in "HH:MMAM/PM" format to minutes since midnight
  13. int parse_time(const string& time_str) {
  14.     int hour = stoi(time_str.substr(0, 2));
  15.     int minute = stoi(time_str.substr(3, 2));
  16.     string meridian = time_str.substr(5, 2);
  17.  
  18.     if (meridian == "Am" && hour == 12) {
  19.         hour = 0;
  20.     } else if (meridian == "Pm" && hour != 12) {
  21.         hour += 12;
  22.     }
  23.  
  24.     return hour * 60 + minute;
  25. }
  26.  
  27. class Flight {
  28. public:
  29.     string source;
  30.     string destination;
  31.     int departure;
  32.     int arrival;
  33.     int price;
  34.  
  35.     Flight(string source, string destination, string departure, string arrival, int price) {
  36.         this->source = source;
  37.         this->destination = destination;
  38.         this->departure = parse_time(departure);
  39.         this->arrival = parse_time(arrival);
  40.         this->price = price;
  41.     }
  42. };
  43.  
  44. int find_cheapest_flight() {
  45.     // Read the number of flights
  46.     int num_flights;
  47.     cin >> num_flights;
  48.  
  49.     vector<Flight> flights;
  50.     map<string, vector<Flight>> flight_map;
  51.  
  52.     // Skip any potential newline after reading num_flights
  53.     cin.ignore();
  54.  
  55.     // Read all the flight data
  56.     for (int i = 0; i < num_flights; i++) {
  57.         string line;
  58.         getline(cin, line);
  59.  
  60.         // Skip any empty lines
  61.         if (line.empty()) {
  62.             continue;
  63.         }
  64.  
  65.         stringstream ss(line);
  66.         string source, dest, departure, arrival;
  67.         int price;
  68.         ss >> source >> dest >> departure >> arrival >> price;
  69.  
  70.         Flight flight(source, dest, departure, arrival, price);
  71.         flights.push_back(flight);
  72.         flight_map[source].push_back(flight);
  73.     }
  74.  
  75.     // Read start and end cities
  76.     string start, end;
  77.     cin >> start >> end;
  78.  
  79.     // Read the earliest departure and latest arrival time
  80.     string earliest_departure, latest_arrival;
  81.     cin >> earliest_departure >> latest_arrival;
  82.  
  83.     int earliest_departure_time = parse_time(earliest_departure);
  84.     int latest_arrival_time = parse_time(latest_arrival);
  85.  
  86.     // Priority queue for Dijkstra-like search: (cost, current_time, city)
  87.     priority_queue<tuple<int, int, string>, vector<tuple<int, int, string>>, greater<tuple<int, int, string>>> pq;
  88.  
  89.     // Initially add flights that depart after the earliest departure time
  90.     for (const auto& flight : flight_map[start]) {
  91.         if (flight.departure >= earliest_departure_time && flight.arrival <= latest_arrival_time) {
  92.             pq.push(make_tuple(flight.price, flight.arrival, flight.destination));
  93.         }
  94.     }
  95.  
  96.     // Dictionary to track the minimum cost to reach each city
  97.     map<string, int> min_cost;
  98.     map<string, int> arrival_time;
  99.  
  100.     // Start the search
  101.     while (!pq.empty()) {
  102.         int cost, current_arrival;
  103.         string city;
  104.         tie(cost, current_arrival, city) = pq.top();
  105.         pq.pop();
  106.  
  107.         // If we've reached the destination, print the cost
  108.         if (city == end) {
  109.             return cost;
  110.         }
  111.  
  112.         // Skip if this city has already been reached with a cheaper cost or earlier arrival time
  113.         if (min_cost.find(city) != min_cost.end() && (cost > min_cost[city] || (cost == min_cost[city] && current_arrival >= arrival_time[city]))) {
  114.             continue;
  115.         }
  116.  
  117.         // Record the minimum cost and arrival time for this city
  118.         min_cost[city] = cost;
  119.         arrival_time[city] = current_arrival;
  120.  
  121.         // Explore all outgoing flights from the current city
  122.         for (const auto& flight : flight_map[city]) {
  123.             if (flight.departure >= current_arrival && flight.departure >= earliest_departure_time && flight.arrival <= latest_arrival_time) {
  124.                 pq.push(make_tuple(cost + flight.price, flight.arrival, flight.destination));
  125.             }
  126.         }
  127.     }
  128.  
  129.     // If we finished the while loop without reaching the destination city
  130.     return -1;  // Impossible
  131. }
  132.  
  133. int main() {
  134.     int result = find_cheapest_flight();
  135.     if (result == -1) {
  136.         cout << "Impossible" << endl;
  137.     } else {
  138.         cout << result << endl;
  139.     }
  140.     return 0;
  141. }
  142.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
8

Mumbai Delhi 03:00Pm 05:00Pm 3300

Ahmedabad Delhi 05:50Pm 06:45Pm 2000

Hyderabad Mumbai 02:00Pm 03:30Pm 2100

Kochi Bhubaneswar 12:00Pm 02:00Pm 4400

Chennai Delhi 04:00Pm 07:00Pm 8500

Mumbai Ahmedabad 04:00Pm 05:45Pm 2700

Chennai Hyderabad 12:00Pm 01:45Pm 1500

Hyderabad Mumbai 10:00Am 12:00Pm 4500

Chennai Delhi

11:00Am 07:00Pm
stdout
copy 
Impossible
https://ideone.com/13rAA1
language:
C++ (gcc 8.3)
created:
6 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!