14938 - 서강그라운드

정보

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

풀이 키워드

스포주의

다익스트라

풀이 코드

정보

• 메모리: 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()

풀이 해설

...

메모

• 이 문제 풀기 전에 택배 배송이랑 파티를 풀어서 특이점이 크게 없었음