본문으로 건너뛰기

14938 - 서강그라운드

info
  • 문제 보기: 14938 - 서강그라운드
  • 소요 시간: 39분 36초
  • 풀이 언어: python
  • 체감 난이도: 2️⃣~3️⃣
  • 리뷰 횟수: ✅

풀이 키워드

스포주의

다익스트라


풀이 코드

info
  • 메모리: 37636 KB
  • 시간: 40 ms
import sys
from math import inf
import heapq
input = sys.stdin.readline

n, m, r = 0, 0, 0
item, graph = [], []

def dijkstra(idx):
distance = [inf] * (n+1)

pq = []
heapq.heappush(pq, (0, idx))
distance[idx] = 0

while pq:
d, cur = heapq.heappop(pq)
if distance[cur] < d:
continue

for v, w in graph[cur]:
cand = d + w
if cand < distance[v]:
heapq.heappush(pq, (cand, v))
distance[v] = cand

res = 0
for i, d in enumerate(distance):
if d <= m:
res += item[i-1]

return res

def solution():
global n, m, r, item, graph

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

for _ in range(r):
v1, v2, w = map(int,input().split())
graph[v1].append((v2, w))
graph[v2].append((v1, w))

ans = 0
for idx in range(1, n+1):
ans = max(ans, dijkstra(idx))

print(ans)


if __name__ == '__main__':
solution()

풀이 해설

...


메모