2300 짜리 다익스트라 문제이다.
https://codeforces.com/contest/1422/problem/D
풀이가 바로 보였는데 원트에 짜서 맞아서 기분이 좋았다.
일단 좌표 차이가 곧 cost인 다익스트라는 꽤 자주 나오는 유형이다. 나는 코포에서 예전에 쳐맞고 배웠는데, 즉 무슨 말이나면 abs(xi-xj)가 곧 cost인 다익스트라는 모든 정점 쌍에 대해 간선을 잇는게 아니라 x좌표가 가장 인접한 쌍에게만 간선을 이어주면 된다.
이 문제는 위 테크닉을 연습하기 좋은 문제라고 볼 수 있다. m개의 정점쌍들에 대해 x좌표 y좌표를 정렬한 후 살펴보면서
인접한 정점 쌍들에 대해서만 간선을 잇는 것이다. 그리고 다익스트라를 돌리고 나서 f와 각각의 정점 사이의 맨해튼 거리를 더해준 것 중 최소값이 정답이 된다.
개인적으로 2300까지는 아니라고 생각한다..
'알고리즘 공부 > codeforces' 카테고리의 다른 글
| Codeforces Round #838 (Div. 2) D.GCD Queries (0) | 2022.12.16 |
|---|---|
| Codeforces Global Round 22 #F. Connectivity Addicts (0) | 2022.10.07 |
| Codeforces Round #717 (Div. 2) C. Baby Ehab Partitions Again (0) | 2022.03.04 |
| Codeforces Round #717 (Div. 2) D. cut (0) | 2021.12.09 |
| Codeforces Global Round 17/ D. Not Quite Lee (0) | 2021.11.29 |