[테스트케이스 추가] 백준 1162번: 도로포장 python, 파이썬

1. 문제

https://www.acmicpc.net/problem/1162

1162번: 도로포장

 

 

 

2. 풀이

cnt라는 차원을 더해서 cnt가 증가했을 때 다익스트라를 구한다.

마치 로또문제를 푸는 것처럼 cnt 없는 경우와 cnt를 하고 거리 값을 추가로 주지 않는 두 가지로 나눠서 q 와 dist를 업데이트한다.

 

 

3. 구현

import sys
import heapq
import math
from collections import deque

sys.stdin=open('input.txt')

N, M, K = map(int, sys.stdin.readline().split())
gph=[[] for _ in range(N+2)]
while M:
  M-=1
  a,b,c = map(int, sys.stdin.readline().split())
  gph[a].append((b,c))
  gph[b].append((a,c))

# node에서 N까지 K를 사용하는 다익스트라
def dijk(node):
  dist=[[math.inf for _ in range(K+2)] for __ in range(N+2)]
  edges=[]
  cnt=0
  dist[node][cnt]=0 #start:1 , end node: 1, cnt: 0
  # pq: cost, pos, cnt
  heapq.heappush(edges,(dist[node][0], 1, cnt))

  while edges:
    cost, pos, cnt = heapq.heappop(edges)
    if dist[pos][cnt]<cost:
      continue
    for p,c in gph[pos]:
      c+=cost
      if dist[p][cnt]>c:
        dist[p][cnt]=c
        heapq.heappush(edges, (c,p,cnt))
      if dist[p][cnt+1]>cost and cnt<K:
        dist[p][cnt+1]=cost
        heapq.heappush(edges,(cost,p,cnt+1))
  return dist

res = dijk(1)
print(min(res[N]))

 

 

 

4. 추가 테스트케이스

 

4 6 1
2 1 1 
2 4 2 
3 4 1 
3 2 2 
4 2 1 
3 1 3

답: 1 

4 6 1
1 2 2 
3 1 2 
1 3 1 
4 2 2 
4 3 1 
3 4 1

답: 1

 

4 6 1
4 3 3 
3 1 3 
2 1 3 
2 4 2 
3 2 3 
1 2 2

답: 2

4 6 1
4 3 3 
3 1 3 
2 1 3 
2 4 200 
3 2 300 
1 2 200

답: 3