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.

Part 1: Compute commute metrics for every mode

You are given an undirected city graph with intersections numbered 0 to N-1. Each road is described by (u, v, allowed_modes), where allowed_modes is a non-empty list of transportation mode IDs. For a fixed mode m, you may travel only on roads whose allowed_modes contains m. Every usable road for mode m takes the same time_per_edge[m] minutes and costs the same cost_per_edge[m] money units. For every mode m in 0 to K-1, compute the minimum number of edges needed to travel from S to D using only roads allowed for that mode. If D is reachable, also compute the total travel time and total travel cost for that mode. If D is not reachable for a mode, mark that mode as invalid with (-1, -1, -1). Return the results for all modes in order.

Constraints

• 1 <= N <= 100000
• 0 <= len(roads) <= 200000
• 1 <= K <= 10
• 0 <= S, D < N
• Each road is undirected
• Each allowed_modes list is non-empty and contains mode IDs in 0..K-1
• time_per_edge[m] and cost_per_edge[m] are non-negative integers

Examples

Example 1

Input: (5, [(0, 1, [0, 1]), (1, 2, [0]), (2, 4, [0, 1]), (0, 3, [1]), (3, 4, [1])], 2, 0, 4, [5, 3], [2, 4])
Output: [(3, 15, 6), (2, 6, 8)]

Explanation: Mode 0 uses path 0-1-2-4 with 3 edges. Mode 1 uses path 0-3-4 with 2 edges.

Example 2

Input: (3, [(0, 1, [0]), (1, 2, [1])], 2, 1, 1, [7, 2], [5, 1])
Output: [(0, 0, 0), (0, 0, 0)]

Explanation: Start equals destination, so every mode reaches D with 0 edges.

Hints

1. For one fixed mode, every usable road has equal weight in terms of edge count, so BFS gives the minimum number of edges.
2. You do not need Dijkstra here. Build the graph once, then run a separate BFS for each mode.

Part 2: Choose the optimal commute mode

You are given the final travel metrics for several commute modes. Each mode is represented by a pair (time, cost). A mode is invalid if its pair is (-1, -1), meaning the destination cannot be reached using that mode. Choose the best valid mode using these rules: smaller total time is better; if times are equal, smaller total cost is better; if both time and cost are equal, any one of those modes may be returned. Return the chosen mode ID together with its (time, cost). If all modes are invalid, return (-1, (-1, -1)). Your algorithm must run in O(K) time and must not sort the list.

Constraints

• 1 <= len(mode_metrics) <= 100000
• Each entry is a tuple (time, cost)
• A valid mode has time >= 0 and cost >= 0
• An invalid mode is represented by (-1, -1)

Examples

Example 1

Input: ([(15, 6), (6, 8), (10, 2)],)
Output: (1, (6, 8))

Explanation: Mode 1 has the smallest total time.

Example 2

Input: ([(-1, -1), (5, 10), (5, 7), (7, 1)],)
Output: (2, (5, 7))

Explanation: Modes 1 and 2 tie on time, so the cheaper one, mode 2, is chosen.

Hints

1. You only need a single pass through the list while keeping track of the current best mode.
2. Update the best answer if you find a smaller time, or the same time with a smaller cost.

Approach

Approach: single linear scan tracking the running best.

The problem reduces to finding the minimum element under a lexicographic key (time, cost) among the valid modes, while reporting that mode's original index. Because the rule "any one may be returned" applies to true ties, we never need to break ties beyond (time, cost) — so a simple one-pass scan suffices and we avoid sorting (which would be O(K log K)).

Key steps:

• Track three running values: best_mode (index, initialized to -1), best_time, and best_cost.
• Iterate with enumerate(mode_metrics) so each candidate carries its original mode index.
• Skip invalid modes with if time < 0 or cost < 0: continue. This handles the (-1, -1) sentinel and is slightly more general (any negative component is treated as invalid, matching "valid mode has time >= 0 and cost >= 0").
• Update the best when either we have no best yet (best_mode == -1), or the candidate is strictly better lexicographically: time < best_time, or time == best_time and cost < best_cost. Using strict < means the first mode encountered among exact ties is kept — consistent with "any one may be returned."

Correctness: The lexicographic comparison exactly encodes the stated priority — minimize time first, then cost as a tiebreak. The invariant "after processing index i, (best_mode, best_time, best_cost) is the best valid mode in [0..i]" holds by induction, so after the full pass it holds for the whole list.

Result: If no valid mode was ever found, best_mode stays -1 and we return (-1, (-1, -1)); otherwise we return (best_mode, (best_time, best_cost)).

• Time complexity: O(K)
• Space complexity: O(1)