하루일문

[백준] 14938번 서강그라운드(파이썬) 본문

algorithm/baekjoon

[백준] 14938번 서강그라운드(파이썬)

support_u 2023. 5. 22. 08:43

문제

 

14938번: 서강그라운드

예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을

www.acmicpc.net

코드

import sys
input = sys.stdin.readline
INF = int(10e9)

city, area, road = map(int, input().split())
item = [0]+list(map(int, input().split()))
ground = [[INF] * (city + 1) for _ in range(city + 1)]

for i in range(road):
    area_1, area_2, dist = map(int, input().split())
    ground[area_1][area_2] = min(ground[area_1][area_2], dist)
    ground[area_2][area_1] = min(ground[area_2][area_1], dist)

for i in range(1, city+1):
    for j in range(1, city+1):
        for k in range(1, city+1):
            if j == k:
                ground[j][k] = 0
            ground[j][k] = min(ground[j][k], ground[j][i] + ground[i][k])

max_item = 0

for i in range(1, city + 1):
    cnt = 0
    for j in range(1, city + 1):
        if ground[i][j] <= area:
           cnt +=  item[j]
    max_item = max(max_item, cnt)
print(max_item)

'algorithm > baekjoon' 카테고리의 다른 글

[백준] 1010번 다리 놓기  (0) 2023.07.28
[백준] 1173번 운동  (0) 2023.06.23
[백준] 1058번 친구(파이썬)  (1) 2023.05.20
[백준] 시리얼 번호 (파이썬)  (0) 2023.05.16
[백준] 4153번 직각삼각형(파이썬)  (0) 2023.05.09
'algorithm/baekjoon' Related Articles more