각 행에 세 개의 필드[src, dest, id]가 포함된 n x 3 행렬이 있다고 가정합니다. 이는 버스에 src에서 dest까지의 경로가 있음을 의미합니다. 새 버스를 타려면 한 단위의 돈이 필요하지만 같은 버스에 계속 있으면 한 단위만 지불하면 됩니다. 0번 위치에서 종점(가장 큰 위치)까지 버스를 타는 데 필요한 최소 비용을 찾아야 합니다. 솔루션이 없으면 -1을 반환합니다.
따라서 입력이 다음과 같으면
| 0 | 1 | 0 |
| 1 | 2 | 0 |
| 2 | 3 | 0 |
| 3 | 5 | 1 |
| 5 | 0 | 2 |
위치 0에서 0을 타고 위치 3에서 나올 수 있으므로 출력은 2가 됩니다. 그런 다음 버스 1을 타고 위치 5에 도달합니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 시작:=0
- target :=주어진 행렬의 최대 위치
- adj :=빈 지도
- 연결의 각 src, dest, id에 대해
- adj[src] 끝에 (dest, id) 삽입
- hp :=항목이 있는 힙(0, 시작, -1)
- 본 :=빈 지도
- hp가 비어 있지 않은 동안 do
- (cost, cur_pos, cur_bus) :=힙 hp의 맨 위 요소 및 hp에서 맨 위 삭제
- cur_pos가 대상과 같으면
- 반품 비용
- 보인[cur_pos]에 cur_bus가 있으면
- 다음 반복으로 이동
- 보여진[cur_pos]에 cur_bus 삽입
- adj[cur_pos]의 각 (nex_pos, nex_bus)에 대해 수행
- next_cost :=비용
- nex_bus가 cur_bus와 같지 않으면
- next_cost :=next_cost + 1
- 힙 HP에 (next_cost, nex_pos, nex_bus) 삽입
- 반환 -1
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
from collections import defaultdict from heapq import heapify, heappop, heappush class Solution: def solve(self, connections): start = 0 target = max(max(y, x) for y, x, _ in connections) adj = defaultdict(list) for f, t, id in connections: adj[f].append((t, id)) hp = [(0, start, -1)] seen = defaultdict(set) while hp: cost, cur_pos, cur_bus = heappop(hp) if cur_pos == target: return cost if cur_bus in seen[cur_pos]: continue seen[cur_pos].add(cur_bus) for nex_pos, nex_bus in adj[cur_pos]: next_cost = cost if nex_bus != cur_bus: next_cost += 1 heappush(hp, (next_cost, nex_pos, nex_bus)) return -1 ob = Solution() matrix = [ [0, 1, 0], [1, 2, 0], [2, 3, 0], [3, 5, 1], [5, 0, 2] ] print(ob.solve(matrix))
입력
matrix = [[0, 1, 0], [1, 2, 0], [2, 3, 0], [3, 5, 1], [5, 0, 2]]
출력
2