[백준] 25430번 - 다이제스타

📩 출처

문제

??? : 자 얘들아 이건 다이제스타 쓰면 돼, 다이제스타.

준혁 : 다이제스타가 뭐야? (검색한다)

준혁 : 아하! 다이제는 과자 이름이구나. 그럼 스타는 뭐지?

진호 : 스타크래프트 좋아하시잖아~

스타크래프트의 저그들은 커널을 가지고 있다. 커널은 1부터 $N$까지 번호가 붙어 있으며 커널들은 길이가 있는 양방향 연결통로를 통해 연결되어 있다.

저그들은 이 연결통로를 이용하여 시작 커널부터 끝 커널까지 자신들의 주식인 다이제를 운반한다. 저그들은 다이제를 운반할때 항상 전에 이동했던 연결통로보다 더 길이가 긴 연결통로를 이용해야만 한다. 그리고 이러한 이동방법 중 총 이동 거리가 가장 짧은 경로를 이용한다. 만약 한번도 연결통로를 이용한 적이 없다면, 아무 연결통로나 이용 할 수 있다.

저그들은 이 이동 방법을 다이제스타라고 부르기로 했다.

준혁이와 진호는 다이제스타가 어떤 방식으로 이루어지는지 궁금해졌다. 준혁이와 진호를 위해 다이제스타를 구현해보자.

입력

첫째 줄에 커널의 개수 $N$과 연결통로의 개수 $M$가 주어진다. $(1 ≤ N ≤ 50,000, 1 ≤ M ≤ 100,000)$ 

두번째 줄부터 $M$개의 줄에 연결통로를 통해 연결되어 있는 두 커널과 연결통로의 길이가 주어진다. 연결통로의 길이는 $10^7$보다 작거나 같은 양의 정수이다.

입력의 마지막 줄에는 시작 커널의 번호와 끝 커널의 번호가 입력된다.

출력

첫째 줄에 운반을 완료했을 때 저그들의 총 이동 거리를 출력해라. 만약 저그들이 커널을 통해 운반을 완료하는 것이 불가능할 경우 DIGESTA를 출력해야 한다.

👉 생각

• 다익스트라와 우선순위 큐를 사용해서 최소 비용으로 최단 거리를 탐색하는 방법이다.
• 이 문제에서 체크해야할 부분이 2가지 있다.
  1. 다음 간선이 이전 간선보다 크기가 커야 함
  2. 비용이 최소인 탐색 경로가 도착점에 도달하지 못할 수 있음
• 1번 같은 경우, 우선 순위 큐에 이전 간선의 크기를 같이 넣어줘서 비교하면 된다.
• 2번 같은 경우, 기존에 누적 비용을 담는 배열과 새로운 누적 비용을 체크해서 작을 때만 큐에 삽입을 해줬지만, 여기서는 그렇게 하면 도착을 못할 수도 있다.
• 따라서, 1번 조건을 만족한다면, 누적 비용을 담는 배열은 더 작은 값으로 넣고 큐에 다가는 누적 비용이 클 지라도 탐색 방법이 존재한다면 일단 넣어준다. 이 탐색 방법이 도착점에 도달할 수 있기 때문!!

import sys, heapq

def dijkstra():
    heap = []
    cost = [sys.maxsize] * (n+1)
    cost[start] = 0
    heapq.heappush(heap, (0, 0, start))
    while heap:
        cur_weight, weight, node = heapq.heappop(heap)

        if node == end:
            return cur_weight

        for new_node, new_weight in adj[node]:
            if new_weight <= weight:
                continue

            tmp = new_weight + cur_weight
            cost[new_node] = min(cost[new_node], tmp)
            heapq.heappush(heap, (tmp, new_weight, new_node))

    return "DIGESTA"

n, m = map(int, sys.stdin.readline().split())
adj = [[] for _ in range(n+1)]
for _ in range(m):
    a, b, c = map(int, sys.stdin.readline().split())
    adj[a].append((b,c))
    adj[b].append((a,c))
start, end = map(int, sys.stdin.readline().split())

print(dijkstra())