Uber is using a city ride network simulation, where intersections are represented as nodes in a graph, and the roads connecting them are represented as edges.

The city has:

n intersections

m bidirectional roads

Each road has travel time.

Each intersection i permanently closes at time close_time[i].

Rules:

Start at node 1 at time 0

If arrival time == close_time[i], it is unreachable

Arrival time must be strictly less than close time

If a driver arrives at an intersection at the exact time it closes, it is considered unreachable. A ride starts at intersection 1 at time 0. Your task is to determine the earliest time each intersection can be reached. If an intersection is unreachable, return -1.

Return the earliest arrival time for every node. If unreachable, return -1.

Function Signature vector<long long> earliestServiceTimes( vector<long long> close_time, vector<int> road_end1, vector<int> road_end2, vector<long long> traveling_time );

Returns vector<long long>: the arrival times at each vertex i, or -1 if the visit is not possible

Example:

In the graph below, the vertices are labeled i/vertex number/time to disappear.

n = 4, m = 4 close_time = [0, 2, 7, 9] road_end1 = [1, 2, 3, 4] road_end2 = [2, 4, 1, 3] traveling_time = [2, 1, 5, 3]

Visit vertex 1 at time = 0 with traversal time = 0. The vertex disappears at time 1. Visit time = 0.

For vertex 2: It takes traveling_time = 2 to traverse from 1 to 2. Arrival time is 2, just as the vertex disappears. Visit time = -1.

From vertex 1 to vertex 3: It takes traveling_time = 5 to traverse between 1 and 3. Arrival time is 0 + 5 = 5, which is before close_time[3] = 7. Visit time = 5.

Move from vertex 3 to vertex 4: It takes traveling_time = 3 to traverse between 3 and 4. Arrival time is 5 + 3 = 8, which is before close_time[4] = 9. Visit time = 8.

The answer array is [0, -1, 5, 8]