199.K最短パスの検索

1.マルチゾーンアルゴリズム

ダイナミックプログラミング

import sys
import heapq
input = sys.stdin.readline
INF = int(1e9)
n, m, k = map(int, input().split())
graph = [dict() for _ in range(n + 1)]
#k까지의 dp 사용, distance의 역할
dp = [[INF] * k for _ in range(n + 1)] 

for _ in range(m):
  a, b, c = map(int,input().split())
  graph[a][b] = c

def dijkstra(start):
  q = []
  heapq.heappush(q, (0, start))
  dp[start][0] = 0
  while q:
    dist, now = heapq.heappop(q)
    for i in graph[now]:
      cost = dist + graph[now][i]
      if cost < dp[i][k-1]:
        dp[i][k-1] = cost
        dp[i].sort()
        heapq.heappush(q, (cost, i))


dijkstra(1)
for i in range(1, n + 1):
  if dp[i][k - 1] == INF:
    print(-1)
  else:
    print(dp[i][k - 1])

優先キュー

import sys
import heapq
input = sys.stdin.readline

def dijkstra(start):
    q = []
    heapq.heappush(q, (0,start))
    distance[1].append(0)
    while q:
        dist, now = heapq.heappop(q)
        for i in graph[now]:
            if len(distance[i]) < k:
                heapq.heappush(distance[i] , -(dist + graph[now][i]))
                heapq.heappush(q, (dist + graph[now][i] , i))
            else:
                if -distance[i][0] > dist + graph[now][i]:
                    heapq.heappop(distance[i])
                    heapq.heappush(distance[i] , -(dist + graph[now][i]))
                    heapq.heappush(q, (dist + graph[now][i] , i))




n, m, k = map(int,input().split())
graph = [ dict() for _ in range(n + 1)]
distance = [ [] for _ in range(n + 1)]
for _ in range(m):
    a, b, c = map(int,input().split())
    graph[a][b] = c

dijkstra(1)
for i in range(1,n+1):
    if len(distance[i]) <k: print(-1)
    else: print(-distance[i][0])