Shipping route cost paths

A parcel carrier publishes its shipping routes as a list of strings. Each string has the form source:target:method:cost:

• source and target are country codes. A route ships one way only.
• method is the carrier or mode (for example Air, Sea, Rail). The same pair of countries can have several routes with different methods.
• cost is a non-negative integer.

Implement a class ShippingNetwork(routes: list[str]) that answers these questions in parts:

1. direct_cost(src, dst) -> int | None. The cheapest single route from src to dst, or None if there is none.
2. all_paths(src, dst, max_legs=2) -> list[Path]. Every way to ship from src to dst using at most max_legs routes (so by default, direct or through one intermediate country). A path must not visit a country twice. Each path lists its legs (source, target, method, cost) and its total cost. Return the paths sorted by total cost, cheapest first.
3. cheapest_path(src, dst) -> Path | None. The cheapest path with any number of stops, or None if dst cannot be reached.

Reject malformed route strings with an error.

Example

routes = ["JP:DE:Air:9", "JP:SG:Sea:2", "SG:DE:Air:4", "JP:DE:Sea:7"]

• direct_cost("JP", "DE") returns 7.
• all_paths("JP", "DE") returns three paths: JP -Sea-> SG -Air-> DE (6), JP -Sea-> DE (7), JP -Air-> DE (9).
• direct_cost("DE", "JP") returns None, because routes are one way.

Example with more stops

routes = ["A:B:x:10", "A:C:y:1", "C:D:z:1", "D:B:w:1"]

• all_paths("A", "B") returns only the direct path (10). The cheaper path needs two stops.
• cheapest_path("A", "B") returns A -> C -> D -> B with cost 3.

Talk through how your design would change if the interviewer adds a limit on the number of stops, or bans some methods or countries.