백준 / 17942 / 알고리즘 공부 / python

from sys import stdin
from heapq import heappop, heapify, heappush
input = stdin.readline

n, m = [int(v) for v in input().split()]

h = []
distant = [0] * (n+1)
visited = [False] * (n+1)
for idx, t in enumerate(map(int, input().split())):
    heappush(h, [t,idx+1])
    distant[idx+1] = t

# print(h, distant)
r = int(input())
r_list = [[] for _ in range(n+1)]
for i in range(r):
    a,b,d = map(int, input().split())
    r_list[a].append((b,d))

_m = 0

z = 0
while h and z < m:
    # print(h)
    # print(distant)
    num, idx = heappop(h)

    if visited[idx]:
        continue
    
    visited[idx] = True
    _m = max(_m, num)

    for m_idx, m_num in r_list[idx]:
        if not visited[m_idx]:
            distant[m_idx] -= m_num
            heappush(h, [distant[m_idx], m_idx])
    
    z += 1
print(_m)

힙 자료구조를 통해 해결할 수 있는 문제

항상 최소 값을 구하면서 진행해야하기 때문에 힙 사용
현재 알고리즘 과목에 대해서 연계되어 빼야할 과목이 있는 경우 빼고 그 값을 저장함과 동시에 뺀 다음에 heap에 넣어 해당 과목에 대해 변경을 반영해 준다.

from sys import stdin
from heapq import heappop, heapify, heappush
input = stdin.readline

n, m = [int(v) for v in input().split()]

h = []
distant = [0] * (n+1)
visited = [False] * (n+1)
for idx, t in enumerate(map(int, input().split())):
    heappush(h, [t,idx+1])
    distant[idx+1] = t

# print(h, distant)
r = int(input())
r_list = [[] for _ in range(n+1)]
for i in range(r):
    a,b,d = map(int, input().split())
    r_list[a].append((b,d))

_m = 0

z = 0
while h and z < m:
    # print(h)
    # print(distant)
    num, idx = heappop(h)

    if distant[idx] < num:
        continue
    
    visited[idx] = True
    _m = max(_m, num)

    for m_idx, m_num in r_list[idx]:
        if distant[m_idx] >  distant[m_idx] - m_num:
            distant[m_idx] -= m_num
            heappush(h, [distant[m_idx], m_idx])
    
    z += 1
print(_m)

처음 방식의 코드로 다익스트라로 해결하려고 했다.
생각해 보면 다익스트라 방법의 경우 이미 끝낸 공부에 대해서도 다시 탐색을 진행하여 결과가 달라질 수 있다.