합승 택시 요금
풀이
본 문제는 다익스트라 알고리즘으로 푸는 문제이다.
승객이 두 명이므로
출발점에서 승객 두명이 헤어지는 지점까지의 최소 비용 + 헤어지는 지점에서 도착점 A 까지의 비용 + 헤어지는 지점에서 도착점 B 까지의 비용
으로 풀면된다.
헤어지는 지점은 결국 완전 탐색으로 모든 정점의 경우를 다 따지면 되고, 출발에서 도착점까지의 비용을 다익스타라 알고리즘을 사용해서 풀면된다.
adj는 주어진 입력에 대해 출발점: [도착점, 비용] 형식으로 나타내었다.
그리고 calculate함수는 출발점 start에 대해 모든 지점까지의 도착 최소 비용을 구했고 end가 내가 원하는 도착지점의 인덱스 이므로 return adj[end] 로 출발에서 도착지점까지의 최소비용 값을 반환해주었다.
solution에서는 경유지점에 대해 완전탐색으로 **출발점에서 승객 두명이 헤어지는 지점까지의 최소 비용 + 헤어지는 지점에서 도착점 A 까지의 비용 + 헤어지는 지점에서 도착점 B 까지의 비용 ** 값을 구해주어 최소 값을 반환하였다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
def calculate(start, end, n, adj):
INF = float('inf')
dist = [INF] * (n+1)
selected = [False] * (n+1)
dist[start] = 0
cnt = 1 # 정점 시작 지점 문제는 1부터 시작이니까
while cnt < n+1:
# dist 가 최소인 정점 찾기
min = INF
u = 1 # 정점 시작 지점 문제는 1부터 시작이니까
for i in range(1,n+1):
if not selected[i] and dist[i] < min:
min = dist[i]
u = i
# 결정
selected[u] = True
cnt += 1
# 간선완화
for w, cost in adj[u]: # 도착정점 w, 가중치 cost
# dist[w] = min(dist[w], dist[u] + cost)
if dist[w] > dist[u] + cost:
dist[w] = dist[u] + cost
return dist[end]
def solution(n,s,a,b,fares):
answer = float('inf')
adj = {i: [] for i in range(1,n+1)} # 인접리스트
for i in range(len(fares)):
x, y, z = fares[i]
adj[x].append([y, z]) # 단방향이기에
adj[y].append([x, z]) # 양방향일 경우
for mid in range(1, n+1):
# 출발에서 헤어지는 지점까지의 비용 + 헤어지는 지점 부터 a 까지 비용 + 헤어지는 지점 부터 b 까지 비용
# 출발에서 헤어지는 지점까지의 비용
now = calculate(s, mid, n, adj) + calculate(mid, a, n, adj) + calculate(mid, b, n, adj)
# print(calculate(s, mid, n, adj))
# print(calculate(mid, a, n, adj))
# print(calculate(mid, b, n, adj))
# print('----')
if answer > now:
answer = now
return answer
fares = [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]]
print(solution(6,4,6,2,fares))