[Python] boj no. 1162 : 도로포장

Problem

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

Idea

1번 도시로부터 N번 도시까지 도달할 때 최대 K번만큼 도로를 비용없이 이용할 수 있는 경우의 최단 경로를 찾는 문제이다.

출발점이 고정되어 있는 최단 경로 문제이므로 다익스트라 알고리즘을 사용하되, 각 정점에 대한 최단 비용 리스트에서 사용한 무료 비용 횟수 마다 최소 비용을 구하는 것으로 해결할 수 있다.

본인은 힙 연산을 이용한 다익스트라 알고리즘을 응용하여 힙 요소를 (비용, 현재 정점, 남은 포장 횟수)의 형태로 하여 구현하였다.

Code

import sys
import heapq

def dijkstra(k):
    heap = []
    visited = [[False for _ in range(N+1)] for _ in range(k+1)]
    dist = [[sys.maxsize for _ in range(N+1)] for _ in range(k+1)]

    heapq.heappush(heap, (0, 1, 0)) # 현재까지의 거리, 현재 정점, 포장 사용 횟수
    dist[0][1] = 0

    while heap:
        pd, pv, pk = heapq.heappop(heap)

        if visited[pk][pv] == False:
            visited[pk][pv] = True

            for nd, nv in edge[pv]:
                if dist[pk][pv] + nd < dist[pk][nv]:
                    dist[pk][nv] = dist[pk][pv] + nd
                    heapq.heappush(heap, (dist[pk][nv], nv, pk))

                if pk < k and dist[pk][pv] <dist[pk+1][nv] :
                    dist[pk+1][nv] = dist[pk][pv]
                    heapq.heappush(heap, (dist[pk+1][nv], nv, pk+1))

    min = sys.maxsize
    for i in dist:
        if i[N] < min:
            min = i[N]

    return min

N, M, K = map(int, sys.stdin.readline().split())
edge = [[] for _ in range(N+1)]
for _ in range(M):
    v1, v2, w = map(int, sys.stdin.readline().split())
    edge[v1].append((w, v2))
    edge[v2].append((w, v1))

print(dijkstra(K))

Comment