[백준] 서강그라운드 (Python 풀이)

Problem Point

시작지점마다 각 노드까지의 거리가 다르므로 모든 노드를 순회하면서 다익스트라를 활용하여 갈 수 있는 노드들을 확인한다. 갈 수 있는 노드를 확인 하고 나서 해당 노드에 들어 있는 item값을 가져온다.

문제출저 : https://www.acmicpc.net/problem/14938

문제에서 요구하는 입력값들을 받은 후에 그래프를 구성하기 위해서 defaultdict를 활용하여 그래프를 만들어 순회한다. 다익스트라 함수를 통해서 각 노드까지의 최단거리를 구하고 거리가 M값보다 작은 노드들에 대해서 item 값들을 더해서 최대값을 구한다.

최종풀이

from collections import deque,defaultdict
import sys

N,M,R=map(int,input().split())
item=[0]+list(map(int,sys.stdin.readline().split()))
dic=defaultdict(lambda :dict())
for i in range(R):
    a,b,c=map(int,sys.stdin.readline().split())
    dic[a][b]=c
    dic[b][a]=c
def dijstra(start):
    distances={node:float('inf') for node in range(1,N+1)}
    distances[start]=0
    queue=deque()
    queue.append([0,start])
    while queue:
        distance,node = queue.popleft()
        if distance > distances[node]:
            continue
        for new_node,new_distance in dic[node].items():
            dis=new_distance+distance
            if dis < distances[new_node]:
                queue.append([dis,new_node])
                distances[new_node]=dis
    return distances

answer=0
for i in range(1,N+1):
    dis=dijstra(i)
    temp=0
    for key,value in dis.items():
        if value<=M:
            temp+=item[key]
    if answer <temp:
        answer=temp
print(answer)