题目重点：A/B分别到某汇合点，之后共用一条路径到D，共享边只计一次。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 有向图、非负权边；两人目标一致，共享尾段不再分开；求联合费用不是两人旅行时间之和。
- 无法让两人到D返回None。无向图需把边添加两个方向；允许汇合点就是A/B/D。
解题路线
- 任取汇合点v，最低费用是distA[v]+distB[v]+distToD[v]。后项需从D在反向图跑Dijkstra，不是从D在原图求distD[v]。
- 对全部v取最小。可行路线给上界；最优路线的最后汇合点给对应下界，因此在共享一次后不分开的合同下公式准确。
- 非负权允许把先合后分再合的路线改成一段共享尾巴而不更差，但若有容量、同时到达、收费折扣随时间或禁止某边共享，就需要新模型。
手动走一遍
A→X=2、B→X=3、X→D=4，另A/B各直达D=10：在X汇合联合费用9，独立最短路和13重复算共享尾段。有向D→X不能代替X→D，即使原图从D可达X，二人也未必能到D。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from heapq import heappush, heappop
def shared_route(n, edges, a, b, dest):
if not 0 <= a < n or not 0 <= b < n or not 0 <= dest < n:
raise ValueError("invalid vertex")
graph, reverse = [[] for _ in range(n)], [[] for _ in range(n)]
for u, v, weight in edges:
if not 0 <= u < n or not 0 <= v < n or weight < 0:
raise ValueError("nonnegative directed edges required")
graph[u].append((v, weight))
reverse[v].append((u, weight))
def distances(g, start):
d = [float('inf')] * n
d[start] = 0
heap = [(0, start)]
while heap:
cost, u = heappop(heap)
if cost != d[u]:
continue
for v, w in g[u]:
new = cost + w
if new < d[v]:
d[v] = new
heappush(heap, (new, v))
return d
da, db, dd = distances(graph,a), distances(graph,b), distances(reverse,dest)
value = min(da[v]+db[v]+dd[v] for v in range(n))
return None if value == float('inf') else value
复杂度
三遍Dijkstra O((V+E)logV)常用复杂度；lazyheap实现更严谨O((V+E)log(V+E))、最坏O(V+E)堆/图空间。
易错点与追问
容易失分的边界
- BFS只适合等权图。
- 三条最短路径可能在v前先重叠，实际联合边费用不会更高；可另选早汇合点达到更小候选。
继续深挖
- 两人出发时间不同但允许免费等待，费用与到达时间怎样分别处理？
- 三人共享路径最小网络为什么不能简单把三个dist相加套同一公式？
