Shipping Route Cost Paths

Problem Overview

A logistics company operates international parcel delivery. Each shipping route is encoded as:

"<source>:<target>:<method>:<cost>"

where source and target are uppercase country codes, method is the carrier, and cost is a positive integer. Given a list of routes and two countries source and target, build three increasingly powerful path queries.

This problem has three progressive parts.

Output Formats (same across all parts)

• Direct route: "A->B;M;C"
• Multi-hop route: "A->B->...->Z;M1->M2->...->Mk;T" — nodes and methods joined with ->, total cost last.

Constraints

• 1 ≤ routes.length ≤ 10⁴
• All country and method names are non-empty uppercase strings.
• source and target are always different.
• No route connects a country to itself.

Part 1: All Paths with At Most One Transfer

Return every path from source to target that uses at most one intermediate country. Both direct edges and any valid two-hop combination should be included. If no such path exists, return an empty list.

Multiple carriers between the same two countries produce multiple distinct paths.

Example

` Input: routes = ["US:UK:FEDEX:5", "US:CA:UPS:1", "CA:FR:DHL:3", "UK:FR:DHL:2"] source = "US", target = "FR"

Output: ["US->CA->FR;UPS->DHL;4", "US->UK->FR;FEDEX->DHL;7"] `

No direct US -> FR route. Two transfer options: US -> CA -> FR (UPS+DHL=4) and US -> UK -> FR (FEDEX+DHL=7).

Part 2: Cheapest Path with At Most One Transfer

Same input shape, same transfer limit, but return a single string — the cheapest path — or "" if no path exists. It's guaranteed that at most one cheapest path exists when a path is possible.

Example

Input: (same as Part 1 Example) Output: "US->CA->FR;UPS->DHL;4"

Part 3: Cheapest Path with Any Number of Transfers

Drop the transfer limit. Find the minimum-cost path through any number of intermediate countries. Return "" if target is unreachable.

Example

` Input: routes = ["US:UK:FEDEX:5", "US:CA:UPS:1", "CA:FR:DHL:3", "UK:FR:DHL:2", "FR:US:DHL:4"] source = "US", target = "FR"

Output: "US->CA->FR;UPS->DHL;4" `

The FR -> US edge is ignored because it doesn't help reach the target at lower cost.

Clarifications Worth Asking

• Can two routes share the same (source, target, method)? Treat them as distinct edges if so.
• Should the same intermediate country appear twice in a Part 3 path? (Shortest-path algorithms naturally avoid this since revisiting never improves the cost on non-negative edges.)
• Is the returned list required to be deterministic? (We sort for stable test output.)

Hint 1 (Part 1): Two-pass enumeration First pass: scan routes and collect direct source -> target matches. Second pass: for each source -> t1 edge (with t1 != target), scan for t1 -> target edges and emit a combined path. O(n + k × n) where n is the number of routes and k is the out-degree of source.

Hint 2 (Part 2): Reduce to Part 1 Reuse find_all_paths, then pick the minimum by cost. Parse the cost from the path string's trailing segment (rsplit(';', 1)[1]). For 10⁴ routes this is fast enough; Part 3 is where you need a real graph algorithm.

Hint 3 (Part 3): Dijkstra with path reconstruction Build an adjacency list country -> [(neighbor, method, cost)]. Run Dijkstra from source. Carry the path (list of nodes and list of methods) in each heap entry so you can reconstruct the full route when you pop target.

Two small gotchas:

• Heap tuples compare element-by-element. If you put a list right after cost, Python will try to compare lists when costs tie. Insert a unique counter (int) between cost and the list fields to break ties safely.
• Use a visited set and skip already-finalized nodes on pop; this is the standard lazy-deletion Dijkstra pattern.

Full Solution (Python) `` Complexity:

• Part 1: O(n²) in the worst case where source has many outgoing routes. Fine for n ≤ 10⁴.
• Part 2: dominated by Part 1; O(n²).
• Part 3: Dijkstra with adjacency list → O((V + E) log V) where V is the number of distinct countries and E = n routes.

Design notes:

• Parsing via split(":") assumes country codes and method names don't contain :. The constraints guarantee uppercase letters, so this is safe.
• Path reconstruction carries two parallel lists (nodes and methods) rather than a single list of (node, method) pairs, because the -> formatting naturally groups nodes together and methods together — mirroring the output spec avoids a second transformation.
• find_cheapest_limited deliberately delegates to find_all_paths instead of re-implementing the search; it's O(n²) either way and the delegation keeps the code compact. For very large inputs you would fold the min directly into the enumeration loop.
• The Dijkstra heap uses a monotonic counter to break ties on equal costs, avoiding list comparison exceptions.

from collections import defaultdict
import heapq


def _parse(routes):
    parsed = []
    for r in routes:
        s, t, m, c = r.split(":")
        parsed.append((s, t, m, int(c)))
    return parsed


def _format(nodes, methods, cost):
    return f"{'->'.join(nodes)};{'->'.join(methods)};{cost}"


def find_all_paths(routes, source, target):
    parsed = _parse(routes)
    results = []

    for s, t, m, c in parsed:
        if s == source and t == target:
            results.append(_format([s, t], [m], c))

    for s1, t1, m1, c1 in parsed:
        if s1 != source or t1 == target:
            continue
        for s2, t2, m2, c2 in parsed:
            if s2 == t1 and t2 == target:
                results.append(_format([source, t1, target], [m1, m2], c1 + c2))

    return sorted(results)


def find_cheapest_limited(routes, source, target):
    paths = find_all_paths(routes, source, target)
    if not paths:
        return ""
    return min(paths, key=lambda p: int(p.rsplit(";", 1)[1]))


def find_cheapest_any(routes, source, target):
    graph = defaultdict(list)
    for s, t, m, c in _parse(routes):
        graph[s].append((t, m, c))

    counter = 0
    heap = [(0, counter, source, [source], [])]
    visited = set()

    while heap:
        cost, _, node, nodes, methods = heapq.heappop(heap)
        if node in visited:
            continue
        visited.add(node)
        if node == target:
            return _format(nodes, methods, cost)
        for nb, m, c in graph[node]:
            if nb not in visited:
                counter += 1
                heapq.heappush(heap, (cost + c, counter, nb, nodes + [nb], methods + [m]))

    return ""