Programmers - 탑승 택시 요금

문제 링크

나는 최단거리를 다익스트라 알고리즘으로 계산했는데 다른 사람들의 풀이에서 보니까
원래 문제의 의도는 플로이드 와샬 알고리즘을 사용해서 푸는 것이라고 한다.

다익스트라 알고리즘 : '한 정점'으로부터 다른 '모든 정점'으로의 최단 경로
플로이드 와샬 알고리즘: '모든 정점'으로부터 다른 '모든 정점'으로의 최단 경로

나의 풀이:
최단경로는 다익스트라 알고리즘으로 계산하고 Case를 4가지로 나누었다.
1) 합승을 하지 않는 경우 : s -> a / s -> b
2) 중간지점까지 같이 타고가는 경우 : s -> stopover / stopover -> a / stopover -> b
3) a먼저 내리고 b 내리는 경우 : s -> a / a -> b
4) b먼저 내리고 a 내리는 경우 : s -> b / b -> a

def solution(n, s, a, b, fares):
    s -= 1
    a -= 1
    b -= 1
    graph = [[-1 for _ in range(n)] for __ in range(n)]
    d = [[-1 for _ in range(n)] for __ in range(n)]

    max_value = 987654321
    for [fr, to, fare] in fares:
        graph[fr-1][to-1] = fare
        graph[to-1][fr-1] = fare

    def dijkstra(x, y):
        if d[x][y] != -1:
            return d[x][y]

        # x -> y 최단거리
        dist = [max_value for _ in range(n)]
        visit = [False for _ in range(n)]
        dist[x] = 0

        while True:
            min_dist = max_value
            node = -1
            for i in range(n):
                if visit[i] or dist[i] == -1:
                    continue
                if min_dist > dist[i]:
                    node = i
                    min_dist = dist[i]
            # 모든 node를 탐색한 경우
            if node == -1:
                break

            visit[node] = True
            for i in range(n):
                if i == node:
                    continue
                if graph[node][i] != -1:
                    dist[i] = min(dist[i], dist[node]+graph[node][i])

        d[x][y] = d[y][x] = dist[y]
        return dist[y]

    no_share = dijkstra(s, a) + dijkstra(s, b)
    # 경유지에서 갈라지는 방법
    via_stopover = max_value
    for stopover in range(n):
        if stopover == a or stopover == b or stopover == s:
            continue
        via_stopover = min(via_stopover, dijkstra(
            s, stopover) + dijkstra(stopover, a) + dijkstra(stopover, b))

    share_ab = dijkstra(s, a) + dijkstra(a, b)
    share_ba = dijkstra(s, b) + dijkstra(b, a)

    return min(no_share, via_stopover, share_ab, share_ba)