여러 나라의 여러 도시를 방문하는 도로 여행을 계획해야 한다고 가정해 보겠습니다. 각 요소가 (x, y, 비용)으로 설명되는 도로 'R' 목록이 있습니다. x는 도로의 출발 도시, y는 도로의 목적지 도시, 비용은 해당 도로를 따라 이동하는 비용을 의미합니다. 또한 각 요소가 국가이고 요소가 해당 국가의 도시를 포함하는 목록 'C'가 있습니다. 이제 출발 도시 '''와 목적지 도시 ''도 있고 출발 도시에서 목적지 도시로 여행을 가려고 합니다. 이 모든 정보를 감안할 때 여행을 완료하기 위해 해야 하는 최소 국가 간 여행 횟수와 여행 총 여행 비용을 알아야 합니다. 이 두 값을 출력으로 인쇄해야 합니다.
따라서 입력이 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입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- cont :=기본값이 0인 새 지도
- 각 인덱스 idx 및 C의 요소 항목에 대해 다음을 수행합니다.
- 항목의 각 k에 대해 다음을 수행합니다.
- 계속[k] :=idx
- 항목의 각 k에 대해 다음을 수행합니다.
- adj_list :=목록을 값으로 포함하는 새 지도
- R의 각, b, wt에 대해 do
- cont[a]가 cont[b]와 같지 않으면
- 중량 :=중량 + 10 ^ 10
- adj_list[a] 끝에 쌍(b, wt) 삽입
- cont[a]가 cont[b]와 같지 않으면
- distance :=기본값이 10 ^ 20인 새 지도
- 거리[s] :=0
- 방문함:=새로운 세트
- t :=(0, s) 쌍을 포함하는 새 힙
- t가 비어 있지 않은 동안 do
- pair (d, c) :=힙에서 가장 작은 항목 팝
- 방문된 항목에 c가 있으면
- 다음 반복으로 이동
- 방문한 항목에 c 추가
- 각 j에 대해 adj_list[c]의 wt, do
- 거리[j]> d + wt이면
- 거리[j] :=d + wt
- 힙 t에 쌍(d + wt, j) 삽입
- 거리[j]> d + wt이면
- 반환 쌍((distance[e] / 10 ^ 10), (distance[e] mod 10 ^ 10)의 바닥 값)
예
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
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)