[BOJ][Python] 백준 14938번 : 서강그라운드

- 문제 링크

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

- 풀이

보통 기본적인 다익스트라 문제는 간선의 비용을 출력하거나 했는데 이 문제는 간선의 비용이 아니라 정점(노드)의 최댓값을 구하는 문제였다. 지문에 보면 양방향 통행이 가능하다고 하니 양방향 그래프로 구현해주면 된다.

 

 1. 거리 배열인 distance 배열을 return 하는 다익스트라를 구현한다. 경로 탐색 중 간선의 비용이 M보다 크다면 생략한다.

 

 2. 1번 노드부터 N번 노드까지 반복을 하며 distance 배열에 INF 값이 아닌 값들의 위치에 있는 아이템의 합을 배열에 넣어준다. 

 

 3. 배열 중에서 제일 큰 값을 출력한다.

 

- 코드

import sys
import heapq
input = sys.stdin.readline
INF = int(1e10)

def dijkstra(start):
    distance = [INF] * (N+1)
    queue = []
    distance[start] = 0
    heapq.heappush(queue, (0, start))
    while queue:
        dist, curr = heapq.heappop(queue)
        if dist > distance[curr]:
            continue


        for next, weight in graph[curr]:
            cost = dist + weight
            if cost > M:
                continue

            if cost < distance[next]:
                distance[next] = cost
                prev[next] = curr
                heapq.heappush(queue, (cost, next))
    return distance

N, M, R = map(int, input().split())
T = [-1] + list(map(int, input().split()))
graph = [[] for _ in range(N+1)]
prev = [0] * (N+1)
for i in range(R):
    a, b, l = map(int, input().split())
    graph[a].append((b, l))
    graph[b].append((a, l))

ans = []
for i in range(1, N+1):
    res = dijkstra(i)
    cnt = 0
    for i in range(len(res)):
        if res[i] != INF:
            cnt += T[i]
    ans.append(cnt)    

print(max(ans))