[ 최단 경로 ] 백준 14938번: 서강그라운드 / 골드 4

https://www.acmicpc.net/problem/14938

14938번: 서강그라운드

 

sol 1) 다익스트라

import heapq
import collections
n, m, r = map(int, input().split())
items = list(map(int, input().split()))
graph = collections.defaultdict(list)
for _ in range(r):
    u, v, w = map(int, input().split())  # start, end, weight
    graph[u].append([v, w])
    graph[v].append([u, w])

def dijkstra(start):
    items_sum = 0
    visit = []
    q = []
    heapq.heappush(q, [0, start])  # [distance, node]
    while q:
        dist, cur = heapq.heappop(q)
        if cur not in visit:
            if dist > m:  # stop searching
                continue
            items_sum += items[cur-1]  # -1 to convert num to idx
            visit.append(cur)
            for next, w in graph[cur]:
                heapq.heappush(q, [dist + w, next])
    return items_sum

answer = 0
for i in range(n):
    answer = max(answer, dijkstra(i+1))  # +1 to convert idx to num
print(answer)

 

sol2) 플로이드-워셜

n, m, r = map(int, input().split())
items = list(map(int, input().split()))
INF = 10**5
graph = [[INF]*n for _ in range(n)]
for i in range(n):
    graph[i][i] = 0
for _ in range(r):
    u, v, w = map(int, input().split())  # start, end, weight
    graph[u-1][v-1] = w  # -1 to convert num to idx
    graph[v-1][u-1] = w

for i in range(n):
    for j in range(n):
        for k in range(n):
            graph[j][k] = min(graph[j][k], graph[j][i] + graph[i][k])

answer = 0
for i in range(n):
    items_sum = 0
    for j in range(n):
        if graph[i][j] <= m:  # valid case
            items_sum += items[j]
    answer = max(answer, items_sum)
print(answer)

 

플로이드- 워셜 풀 때 주의할 점은 플로이드워셜 알고리즘에서 인덱스 순서를 잘 지켜야 한다.

처음에 상관없는 줄 알고

graph[i][k] = min(graph[i][k], graph[i][j] + graph[j][k])

로 했다가 계속 실패했다.