문제

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

풀이 1 (플로이드-워셜)

이 문제는 플로이드-워셜 알고리즘을 사용하거나 다익스트라 알고리즘을 사용해서 풀 수 있다.

플로이드-워셜 알고리즘을 사용하려면 일단 입력을 받고 거리 리스트를 초기화 시켜준다. 이후에 삼중 for문을 돌면서 최단 거리를 갱신하면 된다.

import sys
input = sys.stdin.readline
INF = int(1e9)

n,m,r = map(int,input().split())

items = [-1] + list(map(int,input().split()))

distance = [[INF for i in range(n + 1)] for j in range(n + 1)]

for i in range(1,n+1):
    distance[i][i] = 0

for i in range(r):
    a,b,l = map(int,input().split())

    distance[a][b] = l
    distance[b][a] = l

for i in range(1, n + 1):
    for j in range(1, n + 1):
        for k in range(1, n + 1):
            if distance[j][k] > distance[j][i] + distance[i][k]:
                distance[j][k] = distance[j][i] + distance[i][k]

result = 0

for i in range(1,n + 1):
    temp = 0
    for j in range(1, n + 1):
        if distance[i][j] <= m:
            temp += items[j]
    if temp > result:
        result = temp

print(result)

풀이 2 (다익스트라)

다익스트라 알고리즘을 사용한 전형적인 풀이이다.

각 노드에서 한 번씩 다익스트라 알고리즘을 이용해 다른 정점까지의 최단 거리를 구하면 된다.

이후엔 문제에서 구하라고 하는 값을 계산해서 구하면 된다.

import sys
import heapq
input = sys.stdin.readline
INF = int(1e9)

n,m,r = map(int,input().split())

items = list(map(int,input().split()))

graph = [[] for i in range(n + 1)]

for i in range(r):
    a,b,l = map(int,input().split())
    graph[a].append((b,l))
    graph[b].append((a,l))

result = 0

for i in range(1,n + 1):
    distance = [INF] * (n + 1)
    q = []
    heapq.heappush(q,(0,i))
    distance[i] = 0
    while q:
        dist,now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q,(cost,i[0]))
    temp = 0
    for i,d in enumerate(distance):
        if d <= m:
            temp += items[i - 1]
    if temp > result:
        result = temp

print(result)