[백준] 16118 달빛 여우 [Python, 파이썬]

• 문제 : https://www.acmicpc.net/problem/16118
• 🔑 다익스트라 업그레이드 버전 (최소 거리 리스트가 2차원)
  • 🌙 달빛 여우는 근본 다익스트라로 최소 거리를 구함
  • 🌙 달빛 늑대 다익스트라
    
    • 달릴 때, 걸을 때 두 상태를 저장하기 위해 [[INF, INF], [INF, INF], ...] 처럼 하나의 노드에 두 가지 거리 정보를 담는 리스트 생성
    • 달릴 때는 0, 걸을 때는 1로 상태 표시를 함
    • 처음 시작은 달리면서 시작이니까 0으로 설정
    • 달릴 때는 달빛 여우의 2배 속도로 이동 (가중치 / 2로 계산)
    • 걸을 때는 달빛 여우의 2배 느리게 이동 (가중치 * 2로 계산)
  • 달빛 여우, 늑대 모두 구하고 달빛 여우의 거리가 더 짧은 노드가 있으면 카운트 증가

 

from collections import defaultdict
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
graph = defaultdict(list)
for i in range(m):
    a, b, d = map(int, input().split())
    graph[a].append((d, b))
    graph[b].append((d, a))

INF = int(1e9)

def fox_dijkstra():             # 달빛 여우 다익스트라
    distance = [INF] * (n+1)
    distance[1] = 0
    q = []
    heappush(q, (0, 1))
    
    while q:
        now_d, now_n = heappop(q)

        if now_d > distance[now_n]:
            continue

        for next_d, next_n in graph[now_n]:
            new_d = now_d + next_d
            if distance[next_n] > new_d:
                distance[next_n] = new_d
                heappush(q, (new_d, next_n))

    return distance

def wolf_dijkstra():            # 달빛 늑대 다익스트라
    distance = [[INF] * 2 for _ in range(n+1)]
    distance[1][0] = 0
    q = []
    heappush(q, (0, 1, 0))         # 거리, 시작, 늑대 상태(0 달리기, 1 회복)
    
    while q:
        now_d, now_n, now_state = heappop(q)

        if now_d > distance[now_n][now_state]:
            continue

        for next_d, next_n in graph[now_n]:
            if now_state == 0:                      # 달리기
                new_d = now_d + next_d / 2          # 2배 빠르게 이동
                next_state = 1                      
            else:                                   # 회복
                new_d = now_d + next_d * 2          # 2배 느리게 이동
                next_state = 0                  

            if distance[next_n][next_state] > new_d:
                distance[next_n][next_state] = new_d
                heappush(q, (new_d, next_n, next_state))

    return distance

fox_distance = fox_dijkstra()   # 달빛 여우 최소 거리
wolf_distance = wolf_dijkstra() # 달빛 늑대 최소 거리

cnt = 0
for i in range(1, n+1):
    if fox_distance[i] < wolf_distance[i][0] and fox_distance[i] < wolf_distance[i][1]:
        cnt += 1

print(cnt)