백준_5719_거의 최단 경로(해결 못함)

https://www.acmicpc.net/problem/5719

5719번: 거의 최단 경로

내가 푼 방법

> 다익스트라를 여러번 돌린다.

> 시간 초과로 실패....

 

해결 방법

> while문을 줄일수 있는지 살펴봐야겠다.

 

코드

import sys, heapq

 

input = sys.stdin.readline

INF = float('inf')

 

def solve(adjacent, K):

    prev = [-1] * (len(adjacent))    # predecessor

    dist = [INF] * (len(adjacent))   # source로부터의 최소 거리 배열

    dist[K] = 0

 

    priority_queue = []

    heapq.heappush(priority_queue, [0, K])

 

    while priority_queue:

        # 거리가 제일 작은 노드 선택

        current_dist, here = heapq.heappop(priority_queue)

 

        # 인접 노드 iteration

        for there, length in adjacent[here].items():

            next_dist = dist[here] + length

 

            if next_dist < dist[there]:

                dist[there] = next_dist

                prev[there] = here

                heapq.heappush(priority_queue, [next_dist, there])

 

    return dist, prev

 

if __name__ == "__main__":

    while True:

        num_place, num_road = map(int, input().split())

        if not num_road:    #문제 조건 중 0 0이 들어오면 시스템 종료

            sys.exit()

        start, end = map(int, input().split())

 

        adjacent = [{} for _ in range(num_place)]

 

        for _ in range(num_road):

            a, b, p = map(int, input().split())

 

            # 만약 동일한 경로의 간선이 주어질 경우 적은 비용의 간선 선택

            if b in adjacent[a]:

                adjacent[a][b] = min(adjacent[a][b], p)

            else:

                adjacent[a][b] = p

 

        dist, prev = solve(adjacent, start)

 

        max_dist = dist[end]    #첫번 째 거리

        flag = INF      

        copy_end = end

        a = prev[copy_end]

        while a != -1:          #지금 최소 경로를 삭제

            adjacent[a].pop(copy_end)

            copy_end = a

            a = prev[a]

 

        dist, prev = solve(adjacent, start) #경로 삭제 후 다익스트라

 

        flag = dist[end]

        copy_end = end

        a = prev[copy_end]

        while max_dist == flag: #최소 경로와 경로 삭제 후 돌린 후의 경로가 같을 경우

            while a != -1:  #다시 경로 삭제

                adjacent[a].pop(copy_end)

                copy_end = a

                a = prev[a]

            dist, prev = solve(adjacent, start) #다시 다익스트라

            flag = dist[end]

 

        #탈출!!!

        #거리가 inf이면 갈 수 없다는 뜻이므로 -1을 출력

        if dist[end] == float('inf'):

            print(-1)

        else:

            print(dist[end])