백준 1916 최소비용 구하기 문제풀이

문제 

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

1916번: 최소비용 구하기

 

문제 접근 방식

가중치 그래프가 주어지며 특정 도시에서 특정 도시 사이의 최단경로를 구하는 문제이다. 여기서, 간선의 길이는 0보다 크거나 같다는 조건이 있기 때문에 3개의 대표적인 최단 경로 알고리즘 중 다익스트라를 사용하여 문제를 풀었다.

 

 

시간 복잡도

이 문제의 전체 시간복잡도에서 가장 큰 영향을 미치는 것은 다익스트라 알고리즘이다. 다익스트라의 시간복잡도가 O(ElogV) 이고, 노드의 최대 개수가 1000, 간선의 최대 개수가 1e5이기 때문에 시간 내에 동작함을 알 수 있다.

 

 

코드

import sys
import heapq
input=sys.stdin.readline

INF=int(1e9)

def dijkstra(start,end):
    pq=[]
    heapq.heappush(pq,(0,start))
    while pq:
        cost,node=heapq.heappop(pq)
        if cost>=costs[node]:
            continue

        costs[node]=cost

        for next,w in adj[node]:
            n_cost=costs[node]+w
            if n_cost>=costs[next]:
                continue
            heapq.heappush(pq,(n_cost,next))

    return costs[end]


if __name__=='__main__':
    global n,adj,costs
    n=int(input())
    m=int(input())

    adj=[[] for _ in range(n+1)]
    costs=[INF for _ in range(n+1)]
    for _ in range(m):
        u,v,w=map(int,input().split())
        adj[u].append((v,w))
    
    start,end=map(int,input().split())    
    
    print(dijkstra(start,end))