[백준 1916번] 파이썬 - 최소비용 구하기

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

1916번: 최소비용 구하기

 

 

# 조건

• N개의 도시가 있다.
• 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스
• A번째 도시에서 B번째 도시까지 가는데 드는 버스의 최소비용을 출력하라

 

# 입력

• 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고
• 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다.
• 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다.
  • 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다.
  • 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다.
  • 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다.
• 그리고 M+3째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다.
• 출발점에서 도착점을 갈 수 있는 경우만 입력으로 주어진다.

 

# 접근 방법

• 다익스트라를 이용하여 최소 비용을 따라가며 갱신해주면 된다.
• BFS와 HEAPQ를 이용해주는 전형적인 다익스트라 문제

if visited[cur_node] < cur_dist:  
            continue  

위 코드를 통해 시간을 단축시켜주었다.

• 이미 비용이 작다면 아래 갱신을 해주지 않아도 된다. -> 음의 가중치가 없기 때문에

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from collections import defaultdict  
from heapq import heappop, heappush  
  
  
def dijkstra(st, en):  
    visited = [float('inf') for _ in range(N+1)]  
    visited[0], visited[st] = 0, 0  
    q = []  
    heappush(q, (0, st))  
    while q:  
        cur_dist, cur_node = heappop(q)  
        if visited[cur_node] < cur_dist:  
            continue  
        for node, dist in bus[cur_node]:  
            d = visited[cur_node] + dist  
            if visited[node] > d:  
                visited[node] = d  
                heappush(q, (d,node))  
    print(visited[en])  
  
N = int(input())  
M = int(input())  
  
bus = defaultdict(list)  
for _ in range(M):  
    s, e, w = map(int, input().split())  
    bus[s].append((e, w))  
  
start, end = map(int, input().split())  
dijkstra(start, end)