합승 택시 요금

• 합승해서 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 paths; APSP) 알고리즘을 써서 cost[x][y]를 다 구해놓으면 O(n^3)으로 비효율적이지만, 통과는 된다.
  • 이 문제에서는 cost[…][a] = cost[a][…], 이므로 cost[a][…], cost[b][…], cost[s][…]를 각각 다익스트라 알고리즘으로 구하는 편이 좀더 효율적이다. 문제에서 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))

• Dependency: teflib.tgraph.dijkstra