[백준][다익스트라] 14938. 서강그라운드

14938. 서강그라운드

 

• 내 풀이
  • 이미 방문해서 아이템 체크한 경우에는 select에 담아서 한번만 계산하도록 진행
  • 거리가 m보다 넘어가면 pass

BFS는 "모든 간선의 가중치가 동일할 때" 최단 거리를 구하는 데 적합
간선 가중치가 다를 경우, 다익스트라를 이용해야 비용 비교가 가능

import sys
from collections import defaultdict, deque
import heapq
input=sys.stdin.readline

n,m,r=map(int,input().split())
items=[0]+list(map(int,input().split()))
graph=defaultdict(list)
for _ in range(r):
    a,b,c=map(int,input().split())
    graph[a].append((b,c))
    graph[b].append((a,c))

dp=[0 for _ in range(n+1)]
result=0
def dijkstra(start):
    global m,result

    queue=[]
    heapq.heappush(queue,(0,start))
    visited=[float('inf')]*(n+1)
    visited[start]=0
    tmp=items[start]
    selected=set()

    while queue:
        cur_d,cur=heapq.heappop(queue)

        for nxt,nxt_d in graph[cur]:
            if cur_d+nxt_d>m:
                continue
            if visited[nxt]>cur_d+nxt_d:
                visited[nxt]=cur_d+nxt_d
                heapq.heappush(queue,(cur_d+nxt_d,nxt))
                if nxt not in selected:
                    selected.add(nxt)
                    tmp+=items[nxt]

    result=max(result,tmp)

for i in range(1,n+1):
    dijkstra(i)
print(result)

 

• 다른 사람 풀이
  • 각 지역까지의 최단거리를 구하는 dijkstra 진행 후
  • 아이템 체크는 따로 진행
  • heap에서 pop한 거리가 앞서 진행된 거리보다 크면 무시

import sys
import heapq

n, m, r = map(int, input().split())
items = [0] + list(map(int, input().split()))
graph = [[] for _ in range(n + 1)]

#start 노드에서 각 지역까지의 최소 거리 계산
def dijkstra(start):
    dist = [float('inf')] * (n + 1)
    dist[start] = 0
    pq = [(0, start)]  # (현재 거리, 현재 노드)

    while pq:
        cur_dist, cur_node = heapq.heappop(pq)
        if cur_dist > dist[cur_node]:  # 이미 최단 거리보다 크면 무시
            continue

        for next_node, weight in graph[cur_node]:
            new_dist = cur_dist + weight
            if new_dist < dist[next_node]:  # 더 짧은 경로 발견 시 갱신
                dist[next_node] = new_dist
                heapq.heappush(pq, (new_dist, next_node))

    return dist

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

max_items = 0
for i in range(1, n + 1):
    dist = dijkstra(i)
    
	#각 지역에서 시작할 때 얻을 수 있는 최대 아이템 개수 계산
    total_items = sum(items[j] for j in range(1, n + 1) if dist[j] <= m)
    max_items = max(max_items, total_items)
print(max_items())