각각의 목표지점까지의 거리를 하나씩 구하지 말고 집에서 목표지점까지의 거리, 학교에서 목표지점까지의 거리를 배열을 이용해 저장하고 등산 기대값의 최대를 구한다. 모든 목표지점에 대해서 다익스트라를 수행하니 시간이 초과되었다. 백준 17835번과 유사한 문제이다.
https://www.acmicpc.net/problem/17835
17835번: 면접보는 승범이네
첫째 줄에 도시의 수 N(2 ≤ N ≤ 100,000), 도로의 수 M(1 ≤ M ≤ 500,000), 면접장의 수 K(1 ≤ K ≤ N)가 공백을 두고 주어진다. 도시는 1번부터 N번까지의 고유한 번호가 매겨진다. 다음 M개의 줄에 걸쳐
www.acmicpc.net
'알고리즘 문제풀이' 카테고리의 다른 글
| 첨탑 밀어서 부수기(백준 28014) (0) | 2023.09.12 |
|---|---|
| 가장 많은 글자(백준 1371) (1) | 2023.09.09 |
| 근손실(백준18429) (0) | 2023.09.06 |
| 알바생 강호(백준 1758) (0) | 2023.09.06 |
| 게리맨더링(백준 17471) (0) | 2023.09.06 |