[BOJ] Q13308 주유소

[BOJ] Q13308 주유소

Question

Language: Python

Difficulty: Platinum 5

해당 문제는 1162 문제와 유사한 파트로, 최단경로를 구할때 거리 이외 추가 변수인 주유 비용을 고려해야한다.

distance 배열에 추가적으로 주유비용 관련 요소를 추가해야한다.

항상 경로를 순회 할때, 최소 비용의 주유소를 만나게 되면 해당 주유소에 기름을 넣는 것이 최적의 선택지이다.

Algorithm

1. 주유 비용

min_cost=min(min_cost,oil_costs[adj_vertex-1])

다음 노드를 순회하게 되면 기존의 가장 최소 비용을 비교해서 최신화해줘야한다.

1. 거리 최신화

if next_distance * oil_cost + distance < distance[adj_vertex][oil_cost]:
    distance[adj_vertex][oil_cost]=next_distance * oil_cost + distance
    heappush(heap,(distance[adj_vertex][oil_cost],min_cost,adj_vertex))

해당 주유비용에 대해 해당 노드를 거쳐서 가는게 더 비용이 적게 들면 최신화해준다.

Solution

from math import inf
from heapq import heappush,heappop
def solution():
    distances=[[inf] * 2501 for _ in range(n_vertex+1)]
    heap=[]

    distances[1][oil_costs[0]]=0

    heappush(heap,(0,oil_costs[0],1))

    while heap:
        distance,cost,vertex=heappop(heap)

        if vertex==n_vertex:
            return distance
        
        if distance > distances[vertex][cost]:
            continue

        for adj_vertex,next_distance in graph[vertex]:
            next_cost=min(cost,oil_costs[adj_vertex-1])
            if distance + cost * next_distance < distances[adj_vertex][cost]:
                distances[adj_vertex][cost]=distance + cost * next_distance 
                heappush(heap,(distances[adj_vertex][cost],next_cost,adj_vertex))



if __name__ =="__main__":
    n_vertex,n_edge=map(int,input().split())
    graph=[]
    oil_costs=list(map(int,input().split()))
    
    graph=[[] for _ in range(n_vertex+1)]
    
    for _ in range(n_edge):
        v1,v2,distance=map(int,input().split())
        graph[v1].append((v2,distance))
        graph[v2].append((v1,distance))
        
    print(solution())