# 테페리넷

## 테페리넷

### 관리자 전용

ps:problems:programmers:72413

# 합승 택시 요금

ps
링크https://programmers.co.kr/learn/courses/30/lessons/72413
출처프로그래머스
문제 번호72413
문제명합승 택시 요금
레벨Level 3
분류

그래프

시간복잡도O(n^2)
인풋사이즈n<=200
사용한 언어Python
해결날짜2021/01/26
출처2021 KAKAO BLIND RECRUITMENT

## 풀이

• 합승해서 x까지 같이 간 뒤에, x에서 부터는 따로 택시를 타고 a와 b로 간다면 총 요금은 cost[s][x] + cost[x][a] + cost[x][b].
• 모든 x에 대한 cost[s][x], cost[x][a], cost[x][b]의 값을 계산해놓는다면, min_x(cost[s][x] + cost[x][a] + cost[x][b]) 는 O(n)에 계산가능
• 그냥 전체쌍 최단 경로 (All-pairs shortest path) 알고리즘을 써서 cost[x][y]를 다 구해놓으면 O(n^3)으로 비효율적이지만, 통과는 된다.
• 이 문제에서는 cost[x][a] = cost[a][x], 이므로 cost[a][x], cost[b][x], cost[s][x]를 각각 다익스트라 알고리즘으로 구하는 편이 좀더 효율적이다. 문제에서 E≤O(V^2)으로 주어졌으므로, 시간 복잡도를 O(ElogV)대신 O(V^2)으로 표현하는것이 더 나을듯. 실제 구현은 O(ElogV)의 구현으로 처리했다.
• cost를 모두 구했으면, min을 계산하는 것은 O(n)이다.

## 코드

"""Solution code for "Programmers 72413. 합승 택시 요금".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/72413
- Solution link: http://www.teferi.net/ps/problems/programmers/72413
"""

from teflib import tgraph

def solution(n, s, a, b, fares):
wgraph = [{} for _ in range(n)]
for c, d, f in fares:
wgraph[c - 1][d - 1] = wgraph[d - 1][c - 1] = f
dists_s = tgraph.dijkstra(wgraph, s - 1)
dists_a = tgraph.dijkstra(wgraph, a - 1)
dists_b = tgraph.dijkstra(wgraph, b - 1)
return min(dists_s[x] + dists_a[x] + dists_b[x] for x in range(n))

## 토론

댓글을 입력하세요:
X Y I F W

ps/problems/programmers/72413.txt · 마지막으로 수정됨: 2021/01/30 14:24 저자 teferi

### 문서 도구 