用Python找出公路旅行中最少跨国旅行次数的程序
假设我们必须计划一次公路旅行，其中涉及访问来自不同国家的各个城市。我们有一个道路列表“R”，其中每个元素都被描述为（x，y，成本）。x表示道路的起始城市，y表示道路的目的地城市，成本表示通过该道路行驶的成本。我们还有一个列表“C”，其中每个元素是一个国家，一个元素包含该国家的城市。现在，我们还有一个起始城市's'和一个目的地城市'e'，我们想从源城市前往目的地城市。鉴于所有这些信息，我们必须找出完成旅行所需的最少跨国旅行次数以及旅行的总旅行费用。我们必须打印这两个值作为输出。
所以，如果输入像R=[[0,1,2],[1,2,2],[0,2,3],[1,3,3]],C=[[0],[1],[2,3]],s=0,e=3，则输出为(2,5)。
所以，要从0到3，我们走路径0->1->3。这条路走的路分别是[0,1,2]和[1,3,3]。因此，国家到国家的总旅行为2，总成本为2+3=5。
示例
让我们看看以下实现以获得更好的理解-
from collections import defaultdict
from heapq import heappush, heappop
def solve(R, C, s, e):
cont = defaultdict(int)
for idx, item in enumerate(C):
for k in item:
cont[k] = idx
adj_list = defaultdict(list)
for a, b, wt in R:
if cont[a] != cont[b]:
wt += 10 ** 10
adj_list[a].append((b, wt))
distance = defaultdict(lambda: 10 ** 20)
distance[s] = 0
visited = set()
t = [(0, s)]
while t:
d, c = heappop(t)
if c in visited:
continue
visited.add(c)
for j, wt in adj_list[c]:
if distance[j] > d + wt:
distance[j] = d + wt
heappush(t, (d + wt, j))
return distance[e] //10**10,distance[e]%10**10
print(solve([[0, 1, 2],[1, 2, 2],[0, 2, 3], [1, 3, 3]], [[0],[1],[2, 3]], 0, 3))输入
[[0, 1, 2],[1, 2, 2],[0, 2, 3], [1, 3, 3]], [[0],[1],[2, 3]], 0, 3输出结果
(2, 5)