[파이썬] 백준 14938 : 서강그라운드 (골드 4)

[파이썬] 백준 14938 : 서강그라운드 (골드 4)

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

---

풀이

방향성 생각

• 다익스트라 기본문제
  • 입력에서 노드 번호가 1번부터라서 이 부분만 맞춰주면 된다.
• 다익에서 최소비용을 기록하고 그 비용이 주어진 범위 내에 있으면 아이템을 획득한다.
• 모든 노드에 대해 다익을 돌리고 최대 아이템을 출력한다.

---

전체코드

import heapq as hq
import sys
input = lambda : sys.stdin.readline().rstrip()

N,M,R = map(int,input().split())
items = [0] + list(map(int,input().split()))

G = [[] for _ in range(N+1)]
for _ in range(R):
    a,b,cost = map(int,input().split())
    G[a].append((b,cost))
    G[b].append((a,cost))

def di(m,x):
    heap = []
    hq.heappush(heap,(m,x))
    V = [1e9]*(N+1)
    V[x] = 0
    while heap:
        m,x = hq.heappop(heap)
        for nx,cost in G[x]:
            if V[x] + cost < V[nx]:
                V[nx] = V[x] + cost
                hq.heappush(heap,(m-cost,nx))
    return V

def get_item(V):
    global M
    score = 0
    for idx,val in enumerate(V):
        if val <= M:
            score += items[idx]
    return score

answer = 0
for i in range(1,N+1):
    visit = di(M,i)
    answer = max(answer,get_item(visit))
print(answer)

코멘트

• 알고 너무 오랜만에해서 머리가 멍청해졌음
• IDE cursor로 바꿨는데 글 쓰다보면 알아서 글 써줘서 개꿀인거같음.
• 근데 문제풀때도 자꾸 자기가 풀어서 업로드만 도움받는거로