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:
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,
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.
Add route r to the list of routes that start from r.B.
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.
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.
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.
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.
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.
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.
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.
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 \cdot 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 = 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.
टिप्पणियाँ