11554. Catch the plane

 

Your plane to the ICPC World Finals departs soon, and the only way to reach the airport is by bus. Unfortunately, some drivers are considering going on strike, so you are not sure whether you will arrive on time. Your goal is to plan the trip in such a way as to maximize the probability of catching your flight.

You are given a detailed map of the city showing all bus stations. You are currently at station 0, and the airport is located at station 1. You have the complete schedule: for each bus you know the departure time from its starting station and the arrival time at its destination. Moreover, for every bus you are given the probability that it will actually operate and that its driver will not go on strike. Assume that all these events are independent. In other words, the probability that a particular bus runs according to the schedule does not depend on whether any other bus is running.

If you arrive at a station strictly before a bus departs, you may try to board it. However, if you arrive exactly at the departure time, you will not have enough time to get on the bus. It is impossible to know in advance whether a bus will operate as scheduled – you will only find out at the moment you attempt to board it. If several buses depart from the station at the same time, you may try to board only one of them.

Consider the schedule shown in the figure. It lists the departure and arrival stations for several routes, as well as their departure and arrival times. Next to some of the routes, the probability that the bus will actually operate is given. For routes where the probability is not specified, it is assumed to be 100%.

You may try to take the earliest bus. If it runs, it will take you directly to the airport, and there is nothing to worry about. Otherwise, the situation becomes more complicated. You can take the second bus to station 2. It will certainly depart, but then you will miss the third bus in the list, which would have brought you to the airport in time. The fourth bus you can still catch has a probability of only 0.1 of operating. This is too risky, so it is better to stay at station 0 and wait for the fifth bus. If you manage to board it, you can then try to transfer to the sixth bus to the airport; if it does not run, you will still have a chance to return to station 0 and catch the last bus going directly to the airport.

 

Input. The first line contains two integers m (1 ≤ m ≤ 106) and n (2 ≤ n ≤ 106) – the number of bus routes and the number of stations in the city. The next line contains one integer k (1 ≤ k ≤ 1018) – the time by which you must arrive at the airport.

Each of the following m lines describes one route. Each line contains integers a and b (0 ≤ a, b < n, a ≠ b) – the starting and ending stations. Then follow integers s and t (0 ≤ s < t ≤ k) – the departure time from station a and the arrival time at station b. The last value in the line is a number p (0 ≤ p ≤ 1, with at most 10 digits after the decimal point), denoting the probability that the bus will operate according to the schedule.

 

Output. Print the probability that you will catch your plane if you act optimally. Your answer must have an absolute or relative error of at most 10-6.

 

Sample input 1

Sample output 1

8 4

1000

0 1 0 900 0.2

0 2 100 500 1.0

2 1 500 700 1.0

2 1 501 701 0.1

0 3 200 400 0.5

3 1 500 800 0.1

3 0 550 650 0.9

0 1 700 900 0.1

0.3124

 

 

Sample input 2

Sample output 2

4 2

2

0 1 0 1 0.5

0 1 0 1 0.5

0 1 1 2 0.4

0 1 1 2 0.2

0.7

 

 

SOLUTION

probability

 

Algorithm analysis

To solve the problem, we use a dynamic programming approach where routes are considered in decreasing order of departure time.

Let’s consider the following state:

·        The passenger is at station x at time time.

What is the maximum probability of reaching the airport on time from x under an optimal strategy? We denote this quantity as best(x, time). The parameter time can take values up to 1018, so the number of states is effectively infinite. If we are standing at a station waiting, the situation only changes at moments when a bus departs. Therefore, we’ll consider only bus departure times.

When we compute best(B, S) for a given route, transitions are possible only to states with later times:

·        If the bus runs, we move to the point (E, T),

·        If the bus does not run, we stay at (B, S) and wait for the next route.

In both cases, the next moment in time is strictly later than the current one. Thus, if we process the routes in decreasing order of departure time, all the necessary future values will already have been computed.

 

Dynamic Programming Transitions

Consider the following route:

·        B → E, departure S, arrival T, probability of running p

 

Then there are two possible actions:

1. We try to take the bus. If the bus runs, the probability of this event is p. In this case, we move to the state (E, T) and then continue acting optimally:

p * best(E, next route > T)

If you arrive exactly at the departure time, there is no time left to board the bus. Therefore, we look for the next departure from station E that is strictly greater than T.

 

If the bus is canceled, the probability of this event is 1 – p. In this case, we remain at station B and wait for the next route:

(1 – p) * best(B, next route > S)

If several buses depart from the station at the same time, you can attempt to board only one of them. If that bus is canceled, you cannot board another bus from station B at time S. You must wait for a route whose departure time is strictly greater than S.

 

2. We do not try to take the bus at all. In that case, we move to the next bus at the same station:

best(B, next route ≥ S)

 

Thus, the transition has the following form:

best(B, S) =

max(p * best(E, next route > T) + (1 – p) * best(B, next route > S),

best(B, next route ≥ S))

 

Example

Sort the routes in the first example by station number and departure time. On the right, list the pairs (departure time, route number) sorted by departure time.

 

Route

number

Departure station

Arrival station

Departure time

Arrival time

Probability

Pair

0

0

1

0

900

0.2

(0, 0)

1

0

2

100

500

1.0

(100, 1)

2

0

3

200

400

0.5

(200, 2)

3

0

1

700

900

0.1

(500, 5)

4

1

1

1001

1001

1.0

(500, 7)

5

2

1

500

700

1.0

(501, 6)

6

2

1

501

701

0.1

(550, 8)

7

3

1

500

800

0.1

(700, 3)

8

3

0

550

650

0.9

(1001, 4)

 

Compute the probabilities of arriving at the airport in decreasing order of bus route departure times. The notation time+ denotes a time strictly greater than time.

 

best(1, 1001) = 1.0;

 

best(0, 700) = 0.1 * best(1, 900+) = 0.1 * 1 = 0.1;

 

best(3, 550) = 0.9 * best(0, 650+) + 0.1 * best(3, 550+) = 0.9 * 0.1 = 0.09;

 

best(2, 501) = 0.1 * best(1, 701+) + 0.9 * best(2, 501+) = 0.1 * 1.0 + 0.9 * 0 = 0.1;

 

best(3, 500) = 0.1 * best(1, 800+) + 0.9 * best(3, 500+) =

0.1 * 1.0 + 0.9 * 0.09 = 0.181;

best(3, 500) = max(best(3, 500), best(3, 550)) = max(0.181, 0.09) = 0.181;

 

best(2, 500) = 1.0 * best(1, 700+) + 0.0 * best(2, 500+) = 1.0;

best(2, 500) = max(best(2, 500), best(2, 501)) = max(1.0, 0.1) = 1.0;

 

best(0, 200) = 0.5 * best(3, 400+) + 0.5 * best(0, 200+) =

0.5 * 0.181 + 0.5 * 0.1 = 0.0905 + 0.05 = 0.1405;

best(0, 200) = max(best(0, 200), best(0, 700)) = max(0.1405, 0.1) = 0.1405;

 

best(0, 100) = 1.0 * best(2, 500+) + 0.0 * best(0, 100+) = 1.0 * 0.1 = 0.1;

best(0, 100) = max(best(0, 100), best(0, 200)) = max(0.1405, 0.1) = 0.1405;

 

best(0, 0) = 0.2 * best(1, 900+) + 0.8 * best(0, 0+) =

0.2 * 1.0 + 0.8 * 0.1405 = 0.2 + 0.1124 = 0.3124;

best(0, 0) = max(best(0, 0), best(0, 100)) = max(0.3124, 0.1405) = 0.3124;

 

Algorithm implementation

Define the structure of a bus route, Route. It contains:

·        B – the starting station (where the bus departs from);

·        E – the destination station (where the bus arrives);

·        S – the departure time from the starting station;

·        T – the arrival time at the destination station;

·        P – the probability that the bus will run on the route;

·        value – the maximum probability of reaching the airport (station 1) if the journey starts with this bus and the remaining route is chosen optimally.

 

struct Route

{

  int B, E;

  long long S, T;

  double P, value;

 

Bus routes are sorted:

·        by departure time S

 

  bool operator<(const Route& r) const

  {

    return S < r.S;

  }

};

 

The main part of the program. Read the input data.

 

scanf("%d %d %lld", &m, &n, &k);

 

Create a list of all routes grouped by departure station. The vector v has size n, which is the number of stations. Thus,

·        v[i] contains the list of all bus routes departing from station i.

 

vector<vector<Route>> v(n);

for (int i = 0; i < m; i++)

{

  scanf("%d %d %lld %lld %lf", &r.B, &r.E, &r.S, &r.T, &r.P);

 

The maximum probability of reaching the airport from this route is initially unknown, so we initialize it to 0.

 

  r.value = 0.0;

 

Add route r to the list of routes that start from r.B.

 

  v[r.B].push_back(r);

}

 

Now we create a dummy route that represents the moment when the passenger is already at the airport (station 1). Both the starting and ending stations are the airport.

 

r.B = 1;

r.E = 1;

 

The probability that this route succeeds is 100%.

 

r.value = 1.0;

r.P = 1.0;

 

The departure time and arrival time are later than all others.

 

r.S = k + 1;

r.T = k + 1;

 

Add this dummy route to the list of routes departing from the airport.

 

v[1].push_back(r);

 

For each station i, sort all routes departing from that station (v[i]) by departure time S. This is necessary to efficiently find the next route later using upper_bound.

 

for (int i = 0; i < n; i++)

  sort(v[i].begin(), v[i].end());

 

Create a single processing order for all routes based on departure time so that the dynamic programming can proceed from later routes to earlier ones.

Declare a vector of pairs, ord, which stores for each route:

1.     Departure time S.

2.     Route indices: {i, j}

·        i – station number

·        j – route number in v[i]

Thus, each entry in ord indicates: “Route v[i][j] departs at time S”.

 

vector<pair<long long, pair<int, int>>> ord;

for (int i = 0; i < v.size(); i++)

  for (int j = 0; j < v[i].size(); j++)

    ord.push_back({ v[i][j].S, {i, j} });

 

Sort the vector ord in ascending order of departure times for all routes, regardless of the station.

 

sort(ord.begin(), ord.end());

 

The variable ret computes the maximum probability of catching the flight when starting from station 0 at time 0.

 

double ret = 0.0;

 

Iterate through the routes in decreasing order of departure time, so that for the current route, the value of all future routes (those departing later) has already been computed, allowing us to correctly compute the optimal probability.

 

for (int itOrd = m; itOrd >= 0; itOrd--)

{

 

Let us store the departure time of the current route in the variable startTime.

 

  long long startTime = ord[itOrd].first;

 

p is a pair of indices that allows us to locate the current route in the array of routes v: the route itself is stored in v[p.first][p.second].

 

  auto p = ord[itOrd].second;

 

If the departure time startTime > k (meaning it is impossible to catch the plane), we simply skip this route.

 

  if (startTime > k) continue;

 

st is the index of the departure station for the current route.

 

  int st = p.first;

 

r is the current route for which we compute the value.

 

  Route& r = v[p.first][p.second];

 

Initialize the value for the current route to zero.

 

  r.value = 0.0;

 

query is a temporary object of type Route that is used to find the next route using upper_bound. We do not use all its fields – only B and S, which are needed for comparison during the search.

 

  Route query;

 

Configure query for the following scenario: we want to find the first bus from the same station that departs strictly later than the current time S, if the current bus is canceled (does not run).

 

  query.B = r.B;

  query.S = r.S;

 

We look for the first bus from the same station that departs later.

 

  auto it = upper_bound(v[st].begin() + p.second, v[st].end(), query);

  if (it != v[st].end())

 

If such a route exists, increase r.value by the probability of success through it.

 

    r.value += (1.0 - r.P) * it->value;

 

Consider the scenario where the bus actually runs. In this case, at time T we arrive at station E. We prepare the object query to search for the next route. We formulate the query: “Find a bus that departs from station E later than time T.”

 

  query.B = r.E;

  query.S = r.T;

 

The variable d stores the index of station E, where we have arrived.

 

  int d = r.E;

 

Search for the next bus after arriving at E in the list of routes v[d] using binary search. Its departure time from E must be strictly greater than T, because according to the problem statement, if you arrive exactly at the departure time, you cannot board the bus.

 

  it = upper_bound(v[d].begin(), v[d].end(), query);

  if (it != v[d].end())

 

If such a route is found, it means we can transfer to it. Add the contribution of the probability p * best(E, next route > T).

 

    r.value += r.P * it->value;

 

The next option we consider is to skip the current bus. That is, we do not even consider the option of boarding it or not. We wait for the next bus at the same station.

Check if the next bus exists at this station. Recall that the current route r is stored in v[p.first][p.second].

 

  if (p.second + 1 < v[p.first].size())

 

If the bus exists and the probability of successfully reaching the airport using it is higher, we update value. Here:

·        r.value is the probability of success if we try to board the current bus;

·        v[p.first][p.second + 1].value is the probability of success if we skip the current bus and wait for the next one.

 

    r.value = max(r.value, v[p.first][p.second + 1].value);

 

Update the overall answer. We select the best option only among the buses that depart from the initial (zero) station.

 

  if (r.B == 0) ret = max(ret, r.value);

}

 

Print the answer.

 

printf("%.6lf\n", ret);