[백준 10217번] KCM Travel - python

문제 링크

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

10217번: KCM Travel

풀이 - 다른 블로그 참고 

처음엔 다익스트라로 접근했지만 실패 

최소 비용이 아니라, m 이하의 최소 비용 중에서 최단 시간을 구해야 하기 때문에

단순히 1부터 n까지 가는 최단 비용 경로로 구하면 안된다. 

# 틀린 코드 
import heapq 

INF = int(1e9)
def dijkstra(start, end):
    distance = [INF] * (n+1)
    t_cost = [INF] * (n+1)
    distance[start] = 0 
    q = []
    heapq.heappush(q, (0, 0, start))
    
    while q :
        dist, time, now = heapq.heappop(q)
        
        if distance[now] < dist:
            continue 
        
        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]]= cost 
                t_cost[i[0]]= time + i[2]
                heapq.heappush(q, (cost, t_cost[i[0]], i[0]))
                
    return distance[end], t_cost[end]
        
t = int(input())

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

    cost, time = dijkstra(1, n)  

    min_c, min_t = INF, INF
    for i in range(1,n+1):
        c1, t1 = dijkstra(1, i) 
        c2, t2 =  dijkstra(i, n)
        
        total_c = c1 + c2 
        total_t = t1 + t2
        
        if total_c <= m :
            if total_t < min_t :
                min_c = total_c 
                min_t = total_t

    if min_c == INF:
        print('Poor KCM')
    else:
        print(min_t)

구글링을 통해 찾아보니 이 문제는 dp로 푸는 문제이다. 

냅색 알고리즘 대표 문제

https://zzion2.tistory.com/97

[백준 12865번] 평범한 배낭 -python

따라서 본 문제는 비용의 최댓값이 m으로 정해져있을 때 시간이 최소가 되도록 n까지 이동하는 방법을 구하면 된다. 

knapsack[i][j]는 1에서 i까지 j 비용을 갈 때 최소 시간을 저장한다. 

 

비용을 1원씩 증가시키면서 각 도시들에 대해서 해당 비용으로 이동할 수 있다면, 인접 도시들의 최단 시간을 갱신한다. 

t = int(input())
INF = int(1e9)

for _ in range(t):
    n, m, k = map(int,input().split())
    
    graph = [ [] for _ in range(n+1) ]
    # 1번 도시에서 i번 도시까지 j 비용으로 갔을 때 최단 시간  
    knapsack = [ [INF] * (m+1) for _ in range(n+1)]
    # 1번 도시 최단 시간 초기화 
    knapsack[1][0] = 0
    
    for _ in range(k):
        u, v, c, d = map(int,input().split())
        graph[u].append((v,c,d))
        
    # 모든 비용에 대해서 
    for cost in range(m+1):
    	# 각 도시마다 
        for city in range(1,n+1):
        	# 해당 비용으로 이동할 수 있으면 
            if knapsack[city][cost] != INF :
            	# 인접 도시 최단 시간 갱신 
                for ad_city, c, d in graph[city]:
                	# 이동시간 
                    cal_d = knapsack[city][cost] + d 
                    # 이동 비용 
                    cal_c = cost + c 
                    
                    # 이동 비용이 m 이하이고 더 짧은 시간으로 갈 수 있다면 갱신 
                    if cal_c <= m and cal_d < knapsack[ad_city][cal_c] :
                        knapsack[ad_city][cal_c] = cal_d
                        
    
    # n번 도시까지 가는 최단 시간 구하기 
    result = min(knapsack[n])
    
    # 갈 수 없다면 
    if result == INF:
        print('Poor KCM')
    else:
        print(result)

왜 골드 1인지 알겠다..