这道题是 Stripe "Shipping Cost Calculation" 的后续扩展，难度从单纯的哈希表查找升级到了图论（Graph）与路径搜索。
题目描述
在前一道题中，我们只需要计算两点之间的直接运费。现在，业务场景变得更复杂：
我们需要找出从 Source Country 到 Target Country 的最佳运输路径，并且允许 最多经过一个中转国家。
输入要求
- Shipping Methods: 定义了国家之间的连通性、运输方式（如 FedEx, DHL）和成本。
US -> UK: FedEx ($5), DHL ($7)UK -> FR: UPS ($4)US -> FR: FedEx ($15)
- Query: 起点
US，终点FR。
输出要求
返回一个对象，包含：
route: 路径字符串 (e.g., "US -> UK -> FR")method: 运输方式链 (e.g., "FedEx -> UPS")cost: 总成本
目标：找到成本最低的路径。
oavoservice 解题思路分析
这本质上是一个带约束的最短路径问题（Constrained Shortest Path）。 约束条件是：跳数（Hops）<= 2（直接到达是 1 跳，经过一个中转是 2 跳）。
1. 图的建模
首先，将输入转化为邻接表（Adjacency List）。
graph = {
"US": [ {"to": "UK", "method": "FedEx", "cost": 5}, ... ],
"UK": [ {"to": "FR", "method": "UPS", "cost": 4} ],
...
}
注意：两个国家之间可能有多条边（不同的运输方式），我们需要保留成本最低的那条，或者在搜索时遍历所有边。
2. 搜索策略 (BFS vs DFS)
由于最大深度被限制为 2（起点->终点，或 起点->中转->终点），我们不需要完整的 Dijkstra 算法，简单的遍历即可。
算法流程：
- Direct Path (0 中转): 检查
graph[source]中是否有直接到target的边。记录最低成本min_cost。 - 1-Hop Path (1 中转):
- 遍历
source的所有邻居mid。 - 如果
mid不是target，再检查graph[mid]中是否有到target的边。 - 计算
cost(source->mid) + cost(mid->target)。 - 如果小于当前
min_cost，更新结果。
- 遍历
3. 边界条件
- 无路径：如果无法到达，返回
null或空对象。 - 自环：起点等于终点？通常运费为 0。
- 多条同成本路径：通常返回任意一条即可，或者按 method 字母序排列。
代码片段 (Python)
def find_best_route(source, target, graph):
best_route = None
min_cost = float('inf')
# 1. Check Direct Paths
if source in graph:
for edge in graph[source]:
if edge['to'] == target:
if edge['cost'] < min_cost:
min_cost = edge['cost']
best_route = {
"route": f"{source} -> {target}",
"method": edge['method'],
"cost": min_cost
}
# 2. Check 1-Intermediate Paths
if source in graph:
for edge1 in graph[source]:
mid = edge1['to']
if mid == target: continue # Skip direct
if mid in graph:
for edge2 in graph[mid]:
if edge2['to'] == target:
total_cost = edge1['cost'] + edge2['cost']
if total_cost < min_cost:
min_cost = total_cost
best_route = {
"route": f"{source} -> {mid} -> {target}",
"method": f"{edge1['method']} -> {edge2['method']}",
"cost": min_cost
}
return best_route
面试官会怎么 Follow-up？
- 任意中转次数：如果取消“最多一个中转”的限制？（需升级为 Dijkstra 或 BFS）
- 禁运国家：如果某些国家在黑名单中不能经过？
- 最大成本限制：如果要求成本不能超过 $50？
oavoservice 的面试辅助服务涵盖所有可能的 Follow-up 场景，我们帮你在面试中不仅做对题，还能展现出 senior 级别的思考深度。