ペナルティが最小のグラフ内の2つの頂点間のパスを見つけるプログラム（Python）

無向の重み付きグラフが与えられ、ノードaからノードbへのペナルティを最小限に抑えたパスを見つけるように求められたとします。パスのペナルティは、パス内のすべてのエッジの重みのビットごとのORです。したがって、このような「最小ペナルティ」パスを見つける必要があり、2つのノード間にパスが存在しない場合は、-1を返します。

したがって、入力が次のような場合

開始（s）=1、終了（e）=3;その場合、出力は15になります。

頂点1と3の間に2つのパスがあります。最適なパスは1->2->3で、パスのコストは（10 OR 5）=15です。

これを解決するには、次の手順に従います-

• 関数helper（）を定義します。これにはG、s、e
  が必要です
  • v：=新しいセット
  • c：=値が無限大で初期化されたサイズnの新しいリスト
  • ヒープ：=ペア（0、s）を含む新しいヒープ
  • ヒープのサイズが0より大きい場合は、
    • cst：=ヒープから最小のアイテムをポップします
    • cur：=ヒープから最小のアイテムをポップします
    • c [cur]：=最小値（cst、c [cur]）
    • （cst、cur）がvに存在する場合、
      • 次の反復に進む
    • curがeと同じ場合、
      • return c [cur]
    • ペア（cst、cur）をvに追加
    • ネイバーごとに、G [cur]のn_cost、do
      • 値（（n_cost OR cst）、neighbor）をヒープにプッシュします
  • return c [e]
• G：=[n+1個のエモティリストを含む新しいリスト]
• エッジの各アイテムについて、
  • u：=item [0]
  • v：=item [1]
  • w：=item [2]
  • G [u]の最後にペア（v、w）を挿入します
  • G [v]の最後にペア（u、w）を挿入します
• ans：=helper（G、s、e）
• ansがinfと同じ場合は-1を返し、それ以外の場合はansを返します

例

理解を深めるために、次の実装を見てみましょう-

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