====== 합승 택시 요금 ======

===== 풀이 =====
  * 합승해서 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)에 계산가능
    * 그냥 [[ps:APSP]] 알고리즘을 써서 cost[x][y]를 다 구해놓으면 O(n^3)으로 비효율적이지만, 통과는 된다.
    * 이 문제에서는 cost[...][a] = cost[a][...], 이므로 cost[a][...], cost[b][...], cost[s][...]를 각각 [[ps:단일 출발지 최단 경로#다익스트라 알고리즘]]으로 구하는 편이 좀더 효율적이다. 문제에서 E≤O(V^2)으로 주어졌으므로, 시간 복잡도를 O(ElogV)대신 O(V^2)으로 표현하는것이 더 나을듯. 실제 구현은 O(ElogV)의 구현으로 처리했다.
  * cost를 모두 구했으면, min을 계산하는 것은 O(n)이다.

===== 코드 =====
<dkpr py>
"""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))
</dkpr>
  * Dependency: [[:ps:teflib:tgraph#dijkstra|teflib.tgraph.dijkstra]]

{{tag>프로그래머스 ps:problems:programmers:Level_3}}