[BOJ] 14938 - 서강그라운드 (Python)

 

 

아이디어 #1

 

플로이드-워셜을 이용하여 지역 간 최소 거리를 갱신하고, 획득할 수 있는 최대 아이템 수를 계산한다.

 

 

풀이 #1

 

import sys

input = sys.stdin.readline

def solution():
    n, m, r = map(int, input().split())
    T = [0]+list(map(int, input().split()))
    D = [[150000]*(n+1) for _ in range(n+1)]
    for _ in range(r):
        a, b, l = map(int, input().split())
        D[a][b] = l
        D[b][a] = l
    for k in range(1, n+1):
        D[k][k] = 0
        for i in range(1, n):
            for j in range(i+1, n+1):
                if D[i][k]+D[k][j] < D[i][j]:
                    D[i][j] = D[j][i] = D[i][k]+D[k][j]
    items = [0]*(n+1)
    for i in range(1, n+1):
        items[i] += T[i]
        for j in range(i+1, n+1):
            if D[i][j] <= m:
                items[i] += T[j]
                items[j] += T[i]
    print(max(items))

solution()

 

 

 

아이디어 #2

 

다익스트라를 이용하여 지역 간 최소 거리를 갱신하고, 획득할 수 있는 최대 아이템 수를 계산한다.

 

 

풀이 #2

 

import sys
from heapq import heappush, heappop

input = sys.stdin.readline

def solution():
    n, m, r = map(int, input().split())
    T = [0]+list(map(int, input().split()))
    graph = [[] for _ in range(n+1)]
    for _ in range(r):
        a, b, l = map(int, input().split())
        graph[a].append((l, b))
        graph[b].append((l, a))
    items = [0]*(n+1)
    for i in range(1, n+1):
        D = [150000]*(n+1)
        heap = [(0, i)]
        D[i] = 0
        while heap:
            d, idx = heappop(heap)
            for next_d, next_idx in graph[idx]:
                if d+next_d < D[next_idx]:
                    D[next_idx] = d+next_d
                    heappush(heap, (d+next_d, next_idx))
        items[i] += T[i]
        for j in range(i+1, n+1):
            if D[j] <= m:
                items[i] += T[j]
                items[j] += T[i]
    print(max(items))

solution()