서강그라운드 ( 14938 )

14938번: 서강그라운드

 

나의 풀이

from collections import deque
import sys

def _cr_score(rg_ct, search_range, item_score, conn_dict, go_point):
    answer = 0
    visit = [False] * rg_ct
    visit[go_point - 1] = 0
    queue = deque([(go_point, 0)])

    while queue:
        now_point, now_cost = queue.popleft()
        for next_point, next_cost in conn_dict[now_point]:
            if (now_cost + next_cost <= search_range) and ((visit[next_point - 1] == False) or (visit[next_point - 1]> now_cost + next_cost)):
                visit[next_point - 1] = (now_cost + next_cost)
                queue.append((next_point, now_cost + next_cost))
    for idx in range(rg_ct):
        if (visit[idx] is not False):
            answer += item_score[idx]
    return answer

def _main(rg_ct, search_range, item_score, conn_dict):
    answer = -float('inf')
    for start_point in range(1, rg_ct):
        answer = max(answer, _cr_score(rg_ct, search_range, item_score, conn_dict, start_point))
    return answer

n, m, r = map(int, sys.stdin.readline().rstrip().split())
item_score = tuple(map(int, sys.stdin.readline().rstrip().split()))
conn_dict = {i: [] for i in range(1, n+1)}

for _ in range(r):
    a, b, cost = map(int, sys.stdin.readline().rstrip().split())
    conn_dict[a].append((b, cost))
    conn_dict[b].append((a, cost))

print(_main(n, m, item_score, conn_dict))

 

시간 복잡도

for start_point in range(1, rg_ct) : 시작 포인트 를 순회 ( 선형 시간 복잡도 )
    _cr_score(rg_ct, search_range, item_score, conn_dict, start_point)) : 시작점 기준 수색 범위 탐색 ( 선형 시간 복잡도 )
해당 알고리즘 시간 복잡도 : 이차형 시간 복잡도 ( O(n ** 2) )