[백준] 14938 - 서강그라운드

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

14938번: 서강그라운드

문제 한줄 이해

- 주어진 노드들 사이의 최소 거리를 구하고 제시된 거리보다 낮은 곳을 방문해 최대한 많은 양의 아이템을 구하는 경우를 출력하기

생각난 풀이

1번째 방법: 문제를 읽고 생각난 필요한 조건들

1. 각 노드들 사이의 최소거리 구하기

why? 문제에서 예은이는 정해진 범위 m만큼만 이동 할 수 있다고 한다.

2. 각 노들드의 아이템 수를 담을 리스트를 따로 만들어 놓기

3. 어떤 노드에 예은이가 떨어질지 정해진게 없으므로 모든 노드들의 경우를 구하기

따라서 이 조건들을 적용시키기 위해 다익스트라 알고리즘을 생각했다

import sys
import heapq
n, m, r = map(int,sys.stdin.readline().split())
n_item = list(map(int,sys.stdin.readline().split()))
graph = [[]for i in range(n+1)]

#양방향이기 때문에 a->b b->a 다 가능 하므로 그래프에 저장할때 같이 하기
for i in range(r):
    a, b, i = map(int,sys.stdin.readline().split())
    graph[a].append((b,i))
    graph[b].append((a,i))


def dik(start):
    hq = []
    heapq.heappush(hq,(0,start))
    dis[start] = 0
    while hq:
        nowdis, nown = heapq.heappop(hq)
        
        if nowdis > dis[nown]:
            continue
        
        for i in graph[nown]:
            newdis = i[1] + nowdis
            if newdis < dis[i[0]]:
                dis[i[0]] = newdis
                heapq.heappush(hq,(newdis,i[0]))
                
ans = 0
#예은이가 각 노드에 떨어졌을때 얻을 수 있는 아이템수 구하기
for i in range(1,n+1):
    dis = [1e9] * (n+1)
    dik(i)
    result = 0
    for j in range(1,n+1):
        if dis[j] <= m:
            result += n_item[j-1]
    if result > ans:
        ans = result
print(ans)