728x90
😉 아이디어
1. _!다익스트라(dijkstra) 알고리즘!_ 구현이 포인트
2. _!각자 택시를 타고 목적지로 간 경우 or 중간 목적지까지 함께 이동하고 각자 이동한 cost를 비교!_
😉 풀이
import heapq # 우선순위큐
from math import inf
def solution(n, s, a, b, fares):
graph = [[] for _ in range(n + 1)]
for start, end, cost in fares: # 각 노드와 연결된 edge 체크
graph[start].append([end, cost])
graph[end].append([start, cost])
def dijkstra(start, end):
dist = [inf] * (n + 1)
dist[start] = 0
q = []
heapq.heappush(q, [0, start])
while q:
d, cur = heapq.heappop(q)
if dist[cur] < d:
continue
for edge in graph[cur]:
cost = d + edge[1]
if cost < dist[edge[0]]:
dist[edge[0]] = cost
heapq.heappush(q, [cost, edge[0]])
return dist[end]
# 처음부터 각자 택시를 타고 목적지로 이동
res = dijkstra(s, a) + dijkstra(s, b)
for point in range(1, n + 1):
if point == s: # 함께 이동할 장소가 시작지점과 동일하면 continue
continue
# 목적지로 함께 이동 후 각자 장소로 이동 cost 비교
res = min(res, dijkstra(s, point) + dijkstra(point, a) + dijkstra(point, b))
return res
✔️ 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/72413