✓

태그:

CLASS 4

그래프 상의 모든 점 쌍에 대해 최단 거리가 필요할 때에는 F읍읍…

풀이 비스무리한거 보기

각 지역마다 아이템의 개수와 각 지역을 잇는 길과 플레이어의 파밍 가능한 범위가 주어져있을 때, 파밍 가능한 아이템의 최대 개수를 구하는 문제입니다. 각 지점마다 얻을 수 있는 최대 아이템의 개수를 구하려면 각 지점에 대해 모든 점으로의 최단 거리가 필요합니다. 이는 플로이드-와셜 알고리즘을 사용하면 됩니다. 시간 복잡도가 $O(V^3)$로 조금 느리지만, 이 문제는 입력의 크기가 작기 때문에 시간이 넉넉합니다. 모든 점 쌍에 대해 최단 거리를 구했으면 각 지점마다 수색할 수 있는 지점과 그 지점의 아이템 개수를 구하여 해당 지점에서 시작했을 때 얻을 수 있는 총 아이템 개수의 최대값을 구하면 됩니다.

소스 코드

언어	코드	시간	비고
C++	코드(Github) / 코드(백준)	2021-02-09 23:32:53

---