[boj] 14938_서강 그라운드_python

문제링크

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

14938번: 서강그라운드

---

문제설명

문제

 

입력

첫째 줄에는 지역의 개수 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)가 주어진다.

지역의 번호는 1이상 n이하의 정수이다. 두 지역의 번호가 같은 경우는 없다.

 

출력

예은이가 얻을 수 있는 최대 아이템 개수를 출력한다.

---

문제풀이

import sys, heapq
input = sys.stdin.readline
#  지역의 개수 n (1 ≤ n ≤ 100)과 예은이의 수색범위 m (1 ≤ m ≤ 15), 길의 개수 r (1 ≤ r ≤ 100)
n, m, r = map(int, input().split())
#  n개의 숫자가 차례대로 각 구역에 있는 아이템의 수 t (1 ≤ t ≤ 30)
# 리스트에 저장한 값을 item 배열로 옮겨줌
lst = list(map(int, input().split()))
item = [0 for _ in range(n+1)]
for i in range(1, n+1):
    item[i] = lst[i-1]
res = 0
graph = [[] for _ in range(n+1)]
# 길 양 끝에 존재하는 지역의 번호 a, b, 그리고 길의 길이 l (1 ≤ l ≤ 15)가 주어진다.
# 양 끝에 존재하는 지역의 번호이므로 양방향을 고려하여 a, b 두 경우 다 넣어준다.
for i in range(r):
    a, b, l = map(int, input().split())
    graph[a].append([b, l])
    graph[b].append([a, l])
# 다익스트라를 진행한다.
def dijkstra(t):
    distance = [99999999999 for _ in range(n + 1)]
    q = []
    result = 0
    heapq.heappush(q, [0, t])
    distance[t] = 0
    while q:
        nowCost, nowLoc = heapq.heappop(q)
        if distance[nowLoc] < nowCost:
            continue
        for i in graph[nowLoc]:
            cost = nowCost + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))
    for i in range(1, n+1):
        if distance[i] <= m:
            result += item[i]
    return result

for i in range(1, n+1):
    res = max(res, dijkstra(i))
print(res)

 

---

참고 레퍼런스

 

https://rujang.tistory.com/entry/%EB%B0%B1%EC%A4%80-14938%EB%B2%88-%EC%84%9C%EA%B0%95%EA%B7%B8%EB%9D%BC%EC%9A%B4%EB%93%9C-CC

[백준] 14938번 : 서강그라운드 [C/C++]