[백준] 1916 - 최소비용 구하기

1. 문제

1916번: 최소비용 구하기

2. 개요

N개의 도시가 있고 도시들을 다니는 버스와 그 비용이 주어졌을 때,

시작 도시에서 도착 도시까지 최소 비용을 구하는 문제.

3. 코드 및 추가내용

import sys

MAX_VALUE = 999999999999
N = int(sys.stdin.readline())
M = int(sys.stdin.readline())

graph = [[] for i in range(N+1)]
visited = [0 for i in range(N+1)]
distances = [MAX_VALUE for i in range(N+1)]

for i in range(M):
    s, e, d = map(int, sys.stdin.readline().split())
    graph[s].append([e, d])

start, end = map(int, sys.stdin.readline().split())

distances[start] = 0
visited[start] = 1

for s in graph[start]:
    distances[s[0]] = min(distances[s[0]], s[1])

for _ in range(N-1):
    min_dist = MAX_VALUE
    for i in range(1, N+1):
        if visited[i] == 0 and distances[i] < min_dist:
            min_dist = distances[i]
            now = i

    visited[now] = 1
    for next in graph[now]:
        if distances[now] + next[1] < distances[next[0]]:
            distances[next[0]] = distances[now] + next[1]

print(distances[end])

다익스트라 알고리즘으로 구현한다.

먼저 시작 정점과 연결된 정점들 사이의 비용을 구한 후, 시작 정점은 방문 처리한다.

이후 방문하지 않은 정점 중 최단거리인 정점을 구해 그 정점과 연결된 정점에 대한 처리를 행하는 작업을 반복하면 시작 정점에서 모든 정점까지의 최소비용을 구할 수 있다.