BOJ 1854 K번째 최단경로 찾기

백준 1854 링크

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

문제 풀이

dp[현재위치][k번째로 빨리 도착함]배열을 이용해 풀었습니다.

어제 푼 문제인 도로포장 과 상당히 비슷한 문제라는 생각이 드네요

BOJ 1162 도로포장

 

파이썬으로 문제를 풀다보니까 Cpp랑 다른점이 많이 있네요

input=__import__('sys').stdin.readline

이 한줄이 없으면 시간초과 때문에 Python3로는 통과를 하지 못합니다. pypy3로는 바로 통과하지만...

코드

from heapq import *
input=__import__('sys').stdin.readline
n,m,k = map(int, input().split())
dp=[[float("inf")]*(k) for _ in range(n+1)]
con=[[] for _ in range(n+1)]
for _ in range(m):
    a,b,c=map(int, input().split())
    con[a].append((b,c))
q=[]
heappush(q,(0,1))
dp[1][0]=0
while q:
    cost,now = heappop(q)   
    for next,tcost in con[now]:
        if dp[next][k-1]>cost+tcost:
            dp[next][k-1]=(cost+tcost)
            dp[next]=sorted(dp[next])
            heappush(q,(cost+tcost,next))
for _ in range(1,n+1):
    print(-1 if dp[_][k-1]==float("inf") else dp[_][k-1])