이번 문제는 플로이드-와샬 알고리즘과 다익스트라 알고리즘을 사용하여 두번 풀어보았다.

우선 플로이드-와샬 알고리즘 풀이는 모든 정점에서 모든 정점으로의 최단 거리를 구하여 저장한 후에, 결과값들을 순회하며 최단 거리가 m 이하인 정점에 대한 아이템 수를 더하여 그 중 가장 큰 값을 출력하도록 하였다.

다익스트라 알고리즘 풀이는 다익스트라 알고리즘을 통해 현재 정점에서의 최단 거리를 모두 구하여 리스트로 반환하고, 해당 리스트를 순회하며 m 이하인 정점들의 아이템 수를 더하여 가장 큰 값을 출력하도록 하였다.

Code

우선 플로이드-와샬 풀이이다.

import sys
INF=sys.maxsize
n, m, r=map(int, input().split())
items=[0]+list(map(int, input().split()))
graph=[[INF]*(n+1) for _ in range(n+1)]
for i in range(r):
    a, b, c=map(int, input().split())
    graph[a][b]=min(graph[a][b], c)
    graph[b][a]=min(graph[b][a], c)
for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(1, n+1):
            if i==j:
                graph[i][j]=0
            graph[i][j]=min(graph[i][j], graph[i][k]+graph[k][j])
results=[0 for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(1, n+1):
        if graph[i][j]<=m:
            results[i]+=items[j]
print(max(results))

이번에는 다익스트라 풀이이다.

import heapq, sys
INF=sys.maxsize
input=sys.stdin.readline
def dijkstra(start):
    q=[]
    dist=[INF]*(n+1)
    heapq.heappush(q, [0, start])
    dist[start]=0
    while q:
        dst, cur=heapq.heappop(q)
        if dst>dist[cur]:
            continue
        for nxt_d, nxt in arr[cur]:
            if nxt_d+dst<dist[nxt]:
                nxt_d+=dst
                dist[nxt]=nxt_d
                heapq.heappush(q, [nxt_d, nxt])
    return dist
n, m, r=map(int, input().split())
item=[0]+list(map(int, input().split()))
arr=[[] for _ in range(n+1)]
for _ in range(r):
    start, end, dist=map(int, input().split())
    arr[start].append([dist, end])
    arr[end].append([dist, start])
answer=[0]*(n+1)
for i in range(1, n+1):
    temp=0
    result=dijkstra(i)
    for j in range(1,n+1):
        if result[j]<=m:
            answer[i]+=item[j]
print(max(answer))

다익스트라 풀이가 훨씬 빠른 것을 확인할 수 있었다.