무방향 가중 그래프가 주어지고 노드에서 노드 b까지 가능한 최소 페널티가 있는 경로를 찾으라는 요청을 받았다고 가정합니다. 경로의 페널티는 경로의 모든 가장자리 가중치의 비트 OR입니다. 따라서 이러한 '최소 페널티' 경로를 찾아야 하며, 두 노드 사이에 경로가 없으면 -1을 반환합니다.
따라서 입력이 다음과 같으면
시작(들) =1, 끝(e) =3; 그러면 출력은 15가 됩니다.
정점 1과 3 사이에는 두 개의 경로가 있습니다. 최적 경로는 1->2->3이고 경로 비용은 (10 OR 5) =15입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- helper() 함수를 정의합니다. G, s, e
- v :=새로운 세트
- c :=무한대 값으로 초기화된 크기 n의 새 목록
- heap :=(0, s) 쌍을 포함하는 새 힙
- 힙 크기> 0인 동안 do
- cst :=힙에서 가장 작은 항목 팝
- cur :=힙에서 가장 작은 항목 팝
- c[cur] :=(cst, c[cur])의 최소값
- v에 (cst, cur)가 있으면
- 다음 반복으로 이동
- cur가 e와 같으면
- c[cur]를 반환
- v에 쌍(cst, cur) 추가
- 각 이웃에 대해 G[cur]의 n_cost, do
- 힙에 값((n_cost OR cst), 이웃) 푸시
- 반환 c[e]
- G :=[n + 1개의 이모티콘 목록을 포함하는 새 목록]
- 가장자리의 각 항목에 대해 다음을 수행합니다.
- u :=항목[0]
- v :=항목[1]
- w :=항목[2]
- G[u] 끝에 쌍(v, w) 삽입
- G[v] 끝에 쌍(u, w) 삽입
- ans :=도우미(G, s, e)
- as가 inf와 같으면 -1 반환, 그렇지 않으면 반환
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
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