🥇 14938 서강그라운드
문제
예은이는 낙하산에서 떨어질 때 각 지역에 아이템 들이 몇 개 있는지 알려주는 프로그램을 개발을 하였지만 어디로 낙하해야 자신의 수색 범위 내에서 가장 많은 아이템을 얻을 수 있는지 알 수 없었다.
각 지역은 일정한 길이 l (1 ≤ l ≤ 15)의 길로 다른 지역과 연결되어 있고 이 길은 양방향 통행이 가능하다. 예은이는 낙하한 지역을 중심으로 거리가 수색 범위 m (1 ≤ m ≤ 15) 이내의 모든 지역의 아이템을 습득 가능하다고 할 때, 예은이가 얻을 수 있는 아이템의 최대 개수를 알려주자.
예은이의 수색범위가 4라고 하자. 예은이가 2번 지역에 떨어지게 되면 1번, 2번(자기 지역), 3번, 5번 지역에 도달할 수 있다. (4번 지역의 경우 가는 거리가 이므로 4번 지역의 아이템을 얻을 수 없다.)
이렇게 되면 예은이는 23개의 아이템을 얻을 수 있고, 이는 위의 필드에서 예은이가 얻을 수 있는 아이템의 최대 개수이다.
입력
첫째 줄에는 지역의 개수 n (1 ≤ n ≤ 100)과 예은이의 수색범위 m (1 ≤ m ≤ 15), 길의 개수 r (1 ≤ r ≤ 100)이 주어진다.
둘째 줄에는 n개의 숫자가 차례대로 각 구역에 있는 아이템의 수 t (1 ≤ t ≤ 30)를 알려준다.
세 번째 줄부터 r+2번째 줄 까지 길 양 끝에 존재하는 지역의 번호 a, b, 그리고 길의 길이 l (1 ≤ l ≤ 15)가 주어진다.
출력
예은이가 얻을 수 있는 최대 아이템 개수를 출력한다.
분석
시작 노드에서 다른 모든 노드까지의 거리를 따져야하므로 다익스트라 알고리즘을 사용했다. 노드 시작번호가 0이 아닌 1부터 시작하므로 입력에 주의해야 한다.
기존의 다익스트라 알고리즘에서 cost값을 예은이의 수색범위보다 같거나 작은 기준을 추가해 주었다. 모든 곳을 탐색하고 distance 리스트에서 INF 값이 아닌 노드의 아이템 값만 더해주고 반환한다. 이 값을 계속하여 최댓값으로 갱신해주면 된다.
소스 코드
import sys
from heapq import heappop, heappush
input = sys.stdin.readline
INF = int(1e9)
# 지역 개수, 예은이의 수색범위, 길의 개수
n, m, r = map(int, input().split())
# 각 지역에 있는 아이템 수, n개
items = [0]
items.extend(list(map(int, input().split())))
# 길 양 끝에 존재하는 지역의 번호 a, b, 그리고 길의 길이 l
graph = [[] for _ in range(n+1)]
for _ in range(r):
a, b, l = map(int, input().split())
# 양방향 통행 가능
graph[a].append((b, l))
graph[b].append((a, l))
def dijkstra(start):
distance = [INF for _ in range(n+1)]
distance[start] = 0
q = [(0, start)]
while q:
dist, now = heappop(q)
if distance[now] < dist:
continue
for node, c in graph[now]:
cost = c + dist
# 예은이의 수색범위를 넘어가면 안됨!
if cost <= m and cost < distance[node]:
distance[node] = cost
heappush(q, (cost, node))
total = 0
for i in range(1, n+1):
if distance[i] != INF:
total += items[i]
return total
result = -1
for node in range(1, n+1):
result = max(result, dijkstra(node))
print(result)