[파이썬] 백준 1162 : 도로포장 (플레5)

[파이썬] 백준 1162 : 도로포장 (플레5)

1162번: 도로포장

---

문제

---

풀이

0. 방향성 생각

• 상태 나누기 + 다익스트라
• 벽뿌 시리즈에서 벽을 부순 횟수로 상태 나눈 것 처럼, 도로를 포장한 횟수를 힙에 추가적으로 넣어서 풀이.
• 태그에 DP가 달려있긴 한데 기본적인 발상이 다익이랑 똑같다.

1. 입력

import heapq as hq
import sys
input = lambda : sys.stdin.readline().rstrip()

n,m,k = map(int,input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a,b,cost = map(int,input().split())
    graph[a].append((b,cost)) 
    graph[b].append((a,cost))
    
visit = [[float('inf')]*(n+1) for _ in range(k+1)]
visit[0][1] = 0
heap = [(0,0,1)]
while heap:
    t,skill,x = hq.heappop(heap)
    
    if x == n:
        print(t)
        break
    
    if t > visit[skill][x]:
        continue
    
    for nx,cost in graph[x]:
        nt = t + cost
        if skill < k and t < visit[skill+1][nx]:
            visit[skill+1][nx] = t
            hq.heappush(heap,(t,skill+1,nx))
        if nt < visit[skill][nx]:
            visit[skill][nx] = nt
            hq.heappush(heap,(nt,skill,nx))

• 힙에 (누적 비용, 포장 횟수, 노드)를 넣는다.
• 도착점에 도착했으면 누적비용 출력
• 더미큐 빼주는 코드 추가 (시간초과 방지)
• 도로를 포장할 수 있는 횟수가 남았을 때, 값을 갱신하면 힙에 추가.
• 도로를 포장 안하고 갱신할 수 있으면 힙에 추가.
• if / if문이다. 포장 하는 경우, 안 하는 경우를 동시에 생각해야함.

 

 

코멘트

플레급은 아닌거같은데 흠... 더미큐 안빼주니까 시간초과했음. 더미큐 빼는거를 디폴트로 코드에 추가해야할듯

1e9 대신 inf 쓰니까 통과