백준 10217 KCM Travel - 파이썬

문제.

풀이.

우선 처음에는 다익스트라를 이용하여 풀이를 했다.

처음에는 답이 틀렸다. 그 이유는 비용으로 비교했을때 거리와, 거리로 비교했을때 최소거리 2가지 경우를 모두 생각해야 했었다. 그래서 두 가지 경우를 나눠서 제출을 했는데 이번에는 메모리 초과로 틀렸다. 우선 기존 소스코드를 첨부하겠다.

 

기존 소스코드.

import sys
import heapq

def dijkstra(start):
    global dp
    visited = [False for i in range(N+1)]
    dp_time[start] = [0, 0]
    dp_cost[start] = [0, 0]
    heap = []
    heapq.heappush(heap, [0, start, 0]) #[비용, 위치, 시간]
    while heap:
        now_cost, now, now_time = heapq.heappop(heap)

        if visited[now]:
            continue
        for next, cost, time in graph[now]:
            next_time = now_time + time
            next_cost = now_cost + cost
            if next_time < dp_time[next][0] and next_cost <= M:
                dp_time[next] = [next_time, next_cost]
                heapq.heappush(heap, [next_cost, next, next_time])
            if next_cost < dp_cost[next][0] and next_cost <= M:
                dp_cost[next] = [next_time, next_cost]
                heapq.heappush(heap, [next_cost, next, next_time])


input = sys.stdin.readline
inf = float('inf')
tc = int(input())
for i in range(tc):
    N, M, K = map(int, input().split())
    dp_time = [[inf, 0]] *(N+1) # [시간, 비용]
    dp_cost = [[inf, 0]] *(N+1) # [시간, 비용]
    graph = [[] for i in range(N+1)]
    for j in range(K):
        # c = 비용, d = 소요시간
        u, v, c, d = map(int, input().split())
        graph[u].append([v, c, d])
    dijkstra(1)
    result = min(dp_cost[N][0], dp_time[N][0])

    print(result if result != inf else 'Poor KCM' )

이렇게 해서 틀렸었고 그 다음 풀이에서 맞았다.

pypy3로 제출을 해야 시간 초과가 나지 않는다.

 

소스코드.

import sys

def dijkstra(start):
    dp[start][0] = 0
    for cost in range(M+1):
        for edge in range(1, N+1):
            # 방문하는 dp가 inf 면 생략
            if dp[edge][cost] == inf:
                continue
            now_time = dp[edge][cost] # 현재 소요시간
            for next, next_cost, next_time in graph[edge]:
                # 현재까지의 코스트와 다음 방문에 소요되는 코스트가 총 코스트를 넘으면 생략
                if next_cost + cost > M:
                    continue
                # 방문할려는 위치 ,현재의 코스트 + 방문하기 위한 코스트 값 중 최솟값
                # 다음 방문할려는 곳이 한번도 방문을 안했다면 해당 값이 inf이므로 now_time + next_time으로 갱신됨
                # 그러나 한번 방문된 곳이라면 2가지의 경우의 수 중 최솟 값으로 갱신
                dp[next][next_cost + cost] = min(dp[next][next_cost + cost], now_time + next_time)


input = sys.stdin.readline
inf = float('inf')
tc = int(input())
for i in range(tc):
    N, M, K = map(int, input().split())
    dp = [[inf for r in range(M+1)] for c in range(N+1)]
    graph = [[] for i in range(N+1)]
    for j in range(K):
        # c = 비용, d = 소요시간
        u, v, c, d = map(int, input().split())
        graph[u].append([v, c, d])
    dijkstra(1)
    result = min(dp[N])

    print(result if result != inf else 'Poor KCM' )