728x90
풀이
n개의 정점에 대해 최단거리를 전부 구해준 후, 최단거리가 수색범위(m) 이하인 경우에 대해서 정점이 가지는 아이템의 합들의 최댓값을 구하면 된다.
n개의 정점에 대해 최단거리를 구하기 위해 Floyd Warshall을 사용했다.
n개의 정점에 대한 최단거리를 모두 구한 후,
i번째 정점에서 출발해 수색범위 내로 이동할 수 있는 정점이 가지는 아이템의 합을 구하면 된다.
n개의 정점에 대해 아이템 합의 최댓값을 출력해주면 된다.
소스코드
출처
14938번: 서강그라운드
예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을
www.acmicpc.net
728x90
'PS > Baekjoon Online Judge' 카테고리의 다른 글
| [백준 14442] 벽 부수고 이동하기 2 [Java] (0) | 2023.07.15 |
|---|---|
| [백준 27172] 수 나누기 게임 [Java] (0) | 2023.07.13 |
| [백준 1939] 중량제한 [Java] (0) | 2023.07.09 |
| [백준 2206] 벽 부수고 이동하기 [Java] (0) | 2023.07.09 |
| [백준 21591] Laptop Sticker [Python] (0) | 2023.07.07 |