✅ BOJ 14938 - N번 다익스트라

문제

아이템 수가 주어진 각 지역(노드) 사이를 이동하면서, 예은이가 한 번에 얻을 수 있는 최대 아이템 수를 구하는 문제.

 

전략

핵심은 다익스트라. 모든 노드가 예은이의 시작점이 될 수 있기 때문에 모든 노드를 시작점으로 다익스트라를 돌려야 함.

다익스트라로 구한 최단거리 중, 거리가 m 이하인 노드들의 아이템 수만 누적해서 최댓값을 갱신.

그래프는 무방향이기 때문에 간선 삽입 시 graph[a].append((w, b)), graph[b].append((w, a)) 양쪽 다 넣어야 함.

시간복잡도는 O(N * (E log N)) 정도로 감당 가능.
그냥 다익스트라 여러 번 돌리는 문제라고 보면 됨.

---

# N번 다익스트라 돌리기
import sys,heapq
input=sys.stdin.readline

def dijkstra(start,n,graph):
    INF=float("inf")
    distance=[INF]*n
    distance[start]=0
    
    heap=[]
    heapq.heappush(heap,(0,start))
    
    while heap:
        weight,current_node=heapq.heappop(heap)
        for new_weight,next_node in graph[current_node]:
            cost=weight+new_weight
            if cost<distance[next_node]:
                distance[next_node]=cost
                heapq.heappush(heap,(cost,next_node))
    
    return distance

def find_max_items_cnt(distance,m,nodes):
    total=0
    for i in range(len(distance)):
        if distance[i]<=m:
           total+=nodes[i]
    return total 

def main():
    n,m,r=map(int,input().split())
    nodes=list(map(int,input().split()))
    graph=[[] for _ in range(n+1)]
    max_val=-1

    for _ in range(r):
        start,end,weight=map(int,input().split())
        start-=1
        end-=1
        graph[start].append((weight,end))
        graph[end].append((weight,start))
    
    for i in range(n):
        distance=dijkstra(i,n,graph)
        max_val=max(max_val,find_max_items_cnt(distance,m,nodes))
    
    print(max_val)
        
if __name__=="__main__":
    main()