티스토리 뷰
할인권
문제
그래프가 주어지고 a -> b 경로의 비용이 할인권 k보다 비싸다면 할인권을 사용할 수 있을 때
q개의 여행 경로에 대해서 할인권 사용 횟수를 구하는 문제이다.
문제 풀이
올-페어 최단거리를 구하면 된다.
다익스트라를 n번 돌리거나, 플로이드-워셜 알고리즘을 사용하면 된다.
해당 a->b 최단거리가 k보다 크다면 할인권을 사용하면 된다.
소스 코드
'PS > Codeground' 카테고리의 다른 글
[코드그라운드 연습문제] 두 개의 네비게이션 (2) | 2017.08.27 |
---|---|
[코드그라운드 연습문제] 부분배열 (0) | 2017.04.13 |
[코드그라운드 연습문제] 그릇 모으기 (5) | 2017.04.12 |
[코드그라운드 연습문제] 수강신청 (0) | 2017.04.10 |
[코드그라운드 연습문제] 새로운 방 (0) | 2017.04.10 |
댓글