找出具有最小惩罚的图中两个顶点之间的路径的程序(Python)

假设我们有一个无向的加权图，并被要求找出从节点 a 到节点 b 的惩罚最小的路径。路径的惩罚是路径中所有边的权重的按位或。因此，我们必须找出这样一条“最小惩罚”路径，如果两个节点之间不存在路径，则返回 -1。

所以，如果输入像

开始(s)= 1，结束(e)= 3；那么输出将是 15。

顶点 1 和 3 之间存在两条路径。最优路径为 1->2->3，路径成本为 (10 OR 5) = 15。

示例

让我们看看以下实现以更好地理解 -

import heapq
from math import inf

def helper(G, s, e):
    v = set()
    c = [inf] * len(G)
    heap = [(0, s)]
    while len(heap) > 0:
        cst, cur = heapq.heappop(heap)
        c[cur] = min(cst, c[cur])
        if (cst, cur) in v:
            continue
        if cur == e:
            return c[cur]
        v.add((cst, cur))
        for neighbor, n_cost in G[cur]:
            heapq.heappush(heap, (n_cost | cst, neighbor))
    return c[e]

def solve(n, edges, s, e):
    G = [[] for _ in range(n + 1)]
    for item in edges:
        u, v, w = map(int, item)
        G[u].append((v, w))
        G[v].append((u, w))
    ans = helper(G, s, e)
    return -1 if ans == inf else ans

print(solve(4, [(1, 2, 10), (2, 3, 5), (2, 4, 15), (1, 4, 20)], 1, 3))

输入

4, [(1, 2, 10), (2, 3, 5), (2, 4, 15), (1, 4, 20)], 1, 3

15