[Python 3] BOJ - 14938 "서강그라운드"

 # 문제 링크 : https://www.acmicpc.net/problem/14938

14938번: 서강그라운드

 

 # 풀이 : 

개인적으로 문제의 핵심은 다익스트라 알고리즘을 유추할 수 있는지라고 생각한다. 다익스트라 알고리즘은 출발 정점에서 다른 모든 정점으로 갈 수 있는 최단 거리를 리턴하기 때문에, 모든 정점에 대해 다익스트라 알고리즘을 실행한 후, 만일 입력으로 주어진 수색범위안에 있다면 해당 정점으로 갈 수 있으므로 그때의 정점에 해당하는 아이템을 더해주면 되고, 각 정점에서 얻을 수 있는 모든 아이템들을 비교하여 최대값을 갱신하면 올바른 정답을 구할 수 있다.

 

 # 코드

# 다익스트라의 빠른 실행을 위해 heapq 모듈 import
import heapq, sys

# 최대값 할당
INF = 99999999999999999999999

# 입력부
vertex, limit, edge = map(int, sys.stdin.readline().split())
item = list(map(int, sys.stdin.readline().split()))

# 인접 리스트 생성
adj = [[] for _ in range(vertex)]
for i in range(edge):
    x,y,z = map(int, sys.stdin.readline().split())
    adj[x - 1].append((y - 1, z))
    adj[y - 1].append((x - 1, z))
    
# dijkstra : 다익스트라 알고리즘 함수
def dijstra(v):
    d[v] = 0
    min_q = []
    min_q.append((d[v], v))
    while len(min_q) != 0:
        distance = min_q[0][0]
        current = min_q[0][1]
        heapq.heappop(min_q)
        if d[current] < distance:
            continue
        for i in range(len(adj[current])):
            next = adj[current][i][0]
            nextdistance = adj[current][i][1] + distance
            if nextdistance < d[next]:
                d[next] = nextdistance
                heapq.heappush(min_q, (nextdistance, next))
                
# 각 정점에 대해 다익스트라 실행
ans = 0
for i in range(vertex):
    d = [INF] * vertex
    dijstra(i)
    cnt = item[i]
    for j in range(vertex):
    	# 만일 j가 i가 아니고 수색범위 이내라면
        # cnt에 정점 j에서 얻을 수 있는 아이템 수를 더해줌
        if d[j] != 0 and d[j] <= limit:
            cnt += item[j]
    # 최대값 갱신
    if ans < cnt:
        ans = cnt
print(ans)