https://www.acmicpc.net/problem/1800
문제요약
- 1부터 n까지 학생이 있음(n = 1000)
- P개의 쌍이 연결되어있고 비용이 있음(P = 10000)
- n을 어떻게든 1에 연결하는데 연결 과정에 발생한 비용중에서 k개를 제거하고 남은 것 중에 가장 큰 것이 최종 비용임(0 <= k < n)
- 최종 비용을 최소화
접근법
- 생각을 해야했던 문제
- mst로 접근해야하나 생각했지만 모두가 연결될 필요는 없어서 제외함
- 특정 비용 이하것으로 일단 연결해놓고 나머지로 어떻게 해보자는 방식으로 접근해봄
- 일단 연결해놓고 나머지로 BFS를 돌려서 1 -> n 최단거리를 구하면 좋겠는데 구현이 막막함 : 그룹핑을 다시하고, 간선을 다시 조정하고 하는 등
- 방문 횟수를 카운팅하고, 여기에 우선순위큐를 적용함
- x이하의 비용으로 연결하면 방문횟수 카운팅 안함
- 그렇지 않으면 방문횟수 카운팅
- 방문횟수가 작은 것부터 처리
- x의 값을 조절하면서 성공하면 줄여보고, 실패하면 늘려보고 ==> 파라메트릭서치 + 이분탐색
추가
- 간결하게 다익스트라로 생각하면좋은데, 매끄럽지 않게 생각했었음
- A -> B로 가는 비용이 0 또는 1로 설정하고
- x이하면 비용이 0
- 그렇지 않으면 1
- 1 -> N으로 가는 최소비용을 구하기
- x값을 조절하면서 다익스트라 수행
newbieski