[백준][Python] 1916번 최소비용 구하기 - 그래프, 다익스트라

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

1916번: 최소비용 구하기

 

Python

import sys
input = sys.stdin.readline

v = int(input())
e = int(input())

graph = [[] for _ in range(v+1)]
for _ in range(e):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
start, end = map(int, input().split())

visit = [0]*(v+1)
dist = ["INF"]*(v+1)


def di(start):
    global visit, dist
    dist[start] = 0
    now = start

    for _ in range(v):
        visit[now] = 1
        for x in graph[now]:
            if dist[x[0]] == "INF" or dist[x[0]] > dist[now]+x[1]:
                dist[x[0]] = dist[now]+x[1]

        ans = [int(1e9), 0]  # 전 노드에서 가장 작은 것을 찾아야함
        for i in range(1, v+1):
            if visit[i] == 0 and dist[i] != "INF" and ans[0] > dist[i]:
                ans = [dist[i], i]
        if now == ans[1]:
            break
        now = ans[1]
        #print(dist, visit, now)


di(start)
print(dist[end])