[백준] 14938번 서강그라운드 - 파이썬/다익스트라

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

import heapq

n,m,r = map(int,input().split())

item_list = list(map(int,input().split()))

graph = [ [] for _ in range(n+1) ]



for i in range(r):
    a,b,l = map(int,input().split())
    graph[a].append((b,l))
    graph[b].append((a,l))

q = []

def dij(start):
    INF = int(1e9)
    distance = [INF] * (n + 1)
    item_cnt = 0
    distance[start]=0
    heapq.heappush(q,(0,start))
    while q:

        dist,now = heapq.heappop(q)

        if dist > distance[now]:
            continue

        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]]=cost
                heapq.heappush(q,(cost,i[0]))

    for i in range(1,n+1):
        if distance[i]<=m:
            item_cnt += item_list[i-1]

    return item_cnt

ans = 0

for i in range(1,n+1):
    temt = dij(i)
    if temt>=ans:
        ans=temt

print(ans)

다익스트라 알고리즘의 기본 개념 문제였다.