057 최소비용 구하기

첫번째 코드

 

아직 다익스트라 문제에 익숙해지는 중이다...

이제는 문제도 어렵고.... 해석도 조금씩 어려워지는 느낌 킁...

그래도 꾸준히 책을 따라서 작성해보자

다익스트라를 이용한 문제!

 

import sys
input = sys.stdin.readline
from queue import PriorityQueue

n = int(input())
m = int(input())
distance = [sys.maxsize] * (n+1)
visited = [False] * (n+1)
A = [[] for _ in range(n+1)]

for _ in range(m):
    s, e, w = map(int, input().split())
    A[s].append((e, w))

start, end = map(int, input().split())

def dijstra(start, end):
    queue = PriorityQueue()
    queue.put((0, start))
    distance[start] = 0

    while queue.qsize() > 0:
        nowNode = queue.get()
        now = nowNode[1]

        if not visited[now]:
            visited[now] = True
            for n in A[now]:
                if not visited[n[0]] and distance[n[0]] > distance[now] + n[1]:
                    distance[n[0]] = distance[now] + n[1]
                    queue.put((distance[n[0]], n[0]))
    return distance[end]

print(dijstra(start, end))

 

통과!

코드를 따라 작성하는 것에 우울해하지 말고

다음에 계속 연속해서 풀어보자!

---

링크

https://github.com/ornni/programmers/tree/main/%EB%B0%B1%EC%A4%80/Gold/1916.%E2%80%85%EC%B5%9C%EC%86%8C%EB%B9%84%EC%9A%A9%E2%80%85%EA%B5%AC%ED%95%98%EA%B8%B0

programmers/백준/Gold/1916. 최소비용 구하기 at main · ornni/programmers