BOJ 16118 달빛 여우 python

먼저 일반적인 다익스트라 알고리즘으로 여우의 이동시간을 구해서 dp에 저장해준다. 늑대의 경우에는 빨리 이동해서 도착했을 때, 느리게 이동해서 도착했을 때의 시간을 따로 저장해야 한다. 두 dp를 비교해서 ans를 구한다.

추가시간이 없는 문제라서 파이썬으로 시간초과가 나는 경우가 많은 문제였다. 큐에서 값을 뽑아내고 바로 dp와 비교해서 런타임을 줄일 수 있다. 늑대의 경우는 1번 노드의 값을 초기화 하면 안된다. 경로를 순회해서 빠름-느림 순서를 바꿔주는 경우가 있기 때문이다.

풀이 코드

import sys
from heapq import heappop, heappush
rl = sys.stdin.readline
n, tn = map(int, rl().split())
g = [[] for _ in range(n+1)]
for _ in range(tn):
    u, v, w = map(int, rl().split())
    g[u].append((v,w*2))
    g[v].append((u,w*2))
 
q = [(0,1)]
dp = [1e10 for _ in range(n+1)]
dp[1] = 0
while q:
    t, x = heappop(q)
    if dp[x] < t: continue
    for nx, dt in g[x]:
        if dp[nx] > t+dt:
            dp[nx] = t+dt
            heappush(q,((t+dt, nx)))
 
q = [(0,1,True)]
dp0 = [[1e10]*2 for _ in range(n+1)] #0: 빠르게 도착, 1: 느리게 도착
while q:
    t, x, ch = heappop(q)
    if ch:
        if dp0[x][1] < t: continue
        for nx, dt in g[x]:
            nt = t+dt//2
            if dp0[nx][0] > nt:
                dp0[nx][0] = nt
                heappush(q,(nt, nx, False if ch else True))
    else:
        if dp0[x][0] < t: continue
        for nx, dt in g[x]:
            nt = t+dt*2
            if dp0[nx][1] > nt:
                dp0[nx][1] = nt
                heappush(q,(nt, nx, False if ch else True))
 
ans = 0
for i in range(2,n+1):
    if dp[i] < min(dp0[i]): ans+=1
print(ans)

Desktop View