[파이썬] 백준 10776 : 제국 (골드1)

[파이썬] 백준 10776 : 제국 (골드1)

• https://www.acmicpc.net/problem/10776

---

풀이

방향성 생각

• 같은 node라도 현재 뗏목의 상태에 따라서 다른 상태로 취급한다.
• V에 사용되는 state를 node, hp로 만든다. (입력이 작게 주어지는 이유가 있다. 차원 늘리라고)

 

전체코드

import sys
import heapq as hq

input = lambda : sys.stdin.readline().strip()
INF = float('inf')

# 그래프 추가
K,N,M = map(int,input().split())
G = [[] for _ in range(N+1)]
for _ in range(M):
    a,b,t,h = map(int,input().split())
    G[a].append((b,t,h))
    G[b].append((a,t,h))

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

V = [[INF]*(N+1) for _ in range(K+1)]
V[K][start] = 0

# 다익스트라
heap = [(0,K,start)]
while heap:

    t,hp,x = hq.heappop(heap)

    if t > V[hp][x]:
        continue

    for nx,cost,dmg in G[x]:
        nt = t + cost
        nhp = hp - dmg

        if nhp >= 1 and nt < V[nhp][nx]:
            hq.heappush(heap,(nt,nhp,nx))
            V[nhp][nx] = nt

answer = list(V[i][end] for i in range(1,K+1) if V[i][end] != INF)
print(min(answer) if answer else -1)

코멘트

• 빡구현도 아니고 함수 쓰는걸 선호하지는 않는데, 이런 최단경로 탐색 문제에서는 리턴시키는게 확실히 빠르다.