[백준] 14938. 서강 그라운드 풀이 (Python)

14938번: 서강그라운드

접근한 방법

다른 풀이방법이 많이 있지만 다익스트라 알고리즘으로 풀이합니다. 1번부터 마지막번 노드까지 각각 탐색 시작점을 설정하여 다른 노드까지의 최단 경로 차트를 만든 후 그 안에서 수색 범위(M)안에 해당하는 노드의 아이템 값(items[노드 번호])만 합산해서 최댓값을 구해주면 되는 문제입니다.

코드 풀이 (Python)

import sys
input = sys.stdin.readline

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

// 경로 그래프를 생성합니다. 양방향 그래프임에 주의합니다.
for _ in range(r):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
    graph[b].append((a, c))
from heapq import heappop, heappush
def dijkstra(start):
    visited = [0] * (n + 1) // 방문 체크 배열
    dist = [16] * (n + 1) // start로부터 다른 노드까지의 최단 경로 차트
    dist[start] = 0
    hq = []
    heappush(hq, (0, start))
    while hq:
        d, now = heappop(hq)
        for i in graph[now]: // 현재 연결된 간선 정보 체크
            cost = i[1] + d
            // 아직 방문하지 않은 노드이고 현재 노드를 거친 경로가 기존에 체크했던 경로보다 더 짧으면 갱신
            if cost <= dist[i[0]] and not visited[i[0]]:
                dist[i[0]] = cost
                heappush(hq, (cost, i[0]))
    result = 0
    // 수색 범위 내 아이템 값 합산
    for i in range(1, n + 1):
        if dist[i] == 0 or dist[i] <= m:
            result += items[i]
    return result
result = 0
for i in range(1, n + 1):
    result = max(result, dijkstra(i)) // 최댓값 갱신
print(result)