プログラマー-タクシー料金(2021 KAKAKAO BLIND RECRUITMENT)

プログラマー-タクシー料金(2021 KAKAKAO BLIND RECRUITMENT)

簡単でしたが、提出後に正確性の最後に失敗したので慌てました.どこに問題があるのか見つからず、初期距離の値設定に問題があるようで、100001から10000001に上げるとMAX値が通過しました...料金Fは1以上10万以下の自然水を見ただけで100001という設定で大変でした.N個人の料金がすべて100000であれば、100001は一気に超えるので再設定します.fulieはhipcuを用いたdaostraを用い,まず始点からすべての経路の最短距離を求めた.この後、東からスタート地点まで上がり、降りて、それぞれの家までの距離を解答値に設定します.(始点同乗ではなく、それぞれが行く場合が早いかもしれません)後の始点を除き、すべての地点を起点にaとの最短距離を求め、bとの最短距離後に設定した最高値に比べて最低タクシー代の正解を出すことができます.注意すべきは、始点を除いて、すべての位置で最短距離を求める場合、a点からでもb点からでもよい.この場合、始点の値を0に初期化します.
コードを見ると分かりやすいです.

コード#コード#

import heapq
def dj(start_node,visited,graph,n,a,b):
    visited = [100000001 ] * (n+1)
    route = []
    heapq.heappush(route, (0,start_node))
    while route:
        cost, node = heapq.heappop(route)
        for e_node, e_cost in graph[node]:
            next_cost = e_cost + cost
            if next_cost < visited[e_node]:
                visited[e_node] = next_cost
                heapq.heappush(route,(next_cost,e_node))

    return visited[a], visited[b] , visited

def solution(n, s, a, b, fares):
    # (start_node,visited,graph,n)
    graph = []
    for _ in range(n+1):
        graph.append([])
    for c,d,f in fares:
        graph[c].append((d,f))
        graph[d].append((c,f))
    visited = [1000000] * (n+1)
    ca,cb, tmp_visited = dj(s,visited,graph,n,a,b)
    answer = ca + cb
    for i in range(1,n+1):
        dist = tmp_visited[i]
        if s == i:
            continue
        c_a, c_b, tmp = dj(i,visited,graph,n,a,b)
        #만약 a에서 시작해서 탐색했다면
        if i == a:
            # 거리를 0으로 초기화
            c_a = 0
        if i == b:
            # 해당 거리를 0으로 초기화
            c_b = 0
        dist = dist + c_a + c_b
        answer = min(answer, dist)
    return answer