[백준] [다익스트라 알고리즘] 14938. 서강그라운드

14938. 서강그라운드

14938번: 서강그라운드

 

• 내 풀이
  • 전형적인 다익스트라 문제

#아이템 몇개있는지
#양방향
#지역개수n, 수색범위m, 길 개수 r
import heapq

n,m,r=map(int,input().split())
item=list(map(int,input().split()))
graph=[[] for _ in range(n+1)]


answer=0

def solve(start):
    q=[]
    result = [int(1e9) for _ in range(n + 1)]
    heapq.heappush(q, (0,start))
    result[start]=0

    while q:
        v,x=heapq.heappop(q)

        for gp in graph[x]:
            time, end=gp
            if end == start: continue
            if result[end]>v+time:
                result[end]=v+time
                heapq.heappush(q, (result[end], end))

    count(result)

def count(result):
    global answer
    tmp=0
    for i in range(1,n+1):
        if result[i]<=m:
            tmp+=item[i-1]

    answer=max(answer,tmp)



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


for i in range(1,n+1):
    solve(i)

print(answer)