[Algorithm] 프로그래머스 14938 서강그라운드 | 파이썬 (다익스트라)

※ 14938 서강그라운드

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

 

문제 해결 TIP

최단경로 문제와 동일한 다익스트라 알고리즘으로 구현한다. 이때, 단방향이 아닌 양방향으로 간선 정보를 저장해야 한다. 또한, 수색범위 조건을 추가해준다.

 

전체 코드

import sys
import heapq

input = sys.stdin.readline
INF = int(1e9)

def dijkstra(start):
    q= []
    heapq.heappush(q,(0,start))
    distance[start] = 0

    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            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]))

n, m, r = map(int,input().split())
graph = [[] for _ in range(n+1)]
t = list(map(int,input().split()))
for i in range(r):
    a,b,l = map(int,input().split())
    graph[a].append((b,l))
    graph[b].append((a, l))

result = []
for x in range(1,n+1):
    distance = [INF] * (n + 1)
    dijkstra(x)
    answer = 0
    for i in range(len(distance)):
        if distance[i] <= m:
            answer += t[i-1]
    result.append(answer)
print(max(result))