Find optimal commute mode in a city graph

You are designing a route planner that suggests the best way to commute between two points in a city using different transportation modes.

The city is represented as an undirected graph with N intersections labeled 0 .. N-1 and M roads. There are K possible commute modes (e.g., walk, bike, drive) labeled 0 .. K-1.

Each road is described as:

• u, v — the two endpoints of the road (0-based node indices)
• allowed_modes — a non-empty list of mode IDs in 0 .. K-1 that are allowed to travel on this road

For every mode m:

• If a road is usable by mode m , then traveling along that road:
  • takes time_per_edge[m] minutes
  • costs cost_per_edge[m] units of money

You are also given:

• an integer S — the starting intersection
• an integer D — the destination intersection
• an array time_per_edge[0..K-1]
• an array cost_per_edge[0..K-1]

Task

1. For every commute mode m in 0 .. K-1 , considering only roads whose allowed_modes contains m , compute the minimal number of edges from S to D (if reachable). From that, derive:
   • total travel time T[m] = (number_of_edges_m) * time_per_edge[m]
   • total travel cost C[m] = (number_of_edges_m) * cost_per_edge[m]
   If D is not reachable from S using mode m , then that mode should be considered invalid for the final choice.
2. Among all valid modes that can reach D , select the optimal commute mode according to:
   • smaller total travel time is better;
   • if two modes have the same total travel time, smaller total cost is better;
   • if both time and cost are equal, you may return any one of those modes.

Return:

• the chosen mode ID, and
• the pair (T[mode], C[mode]) for that chosen mode.

If no mode can reach D, return an indication that the destination is unreachable (e.g., -1 as the mode and some sentinel values for time and cost).

Some modes may end up with identical (time, cost) pairs (duplicates); your algorithm must still handle these ties correctly.

Constraints

• 1 <= N <= 10^5
• 0 <= M <= 2 * 10^5
• 1 <= K <= 10
• The graph is sparse and fits in memory using adjacency lists.
• All times and costs are non-negative integers that fit in 32-bit signed integers.

Requirements

• Exploit the fact that for each given mode, all usable roads have the same time and cost per edge. You should not treat this as an arbitrary weighted-graph problem that forces you to use a general algorithm like Dijkstra on a combined weighted graph for all modes.
• The overall graph traversal per mode should run in linear time with respect to the size of the graph for that mode (i.e., O(N + M) per mode or better).
• The final step that chooses the optimal mode from the K (time, cost) pairs must run in O(K) time and must not sort the list of modes.

Describe your approach, discuss its time and space complexity, and then implement the solution in code.