[코드그라운드 연습문제] 할인권

할인권

문제

그래프가 주어지고 a -> b 경로의 비용이 할인권 k보다 비싸다면 할인권을 사용할 수 있을 때

q개의 여행 경로에 대해서 할인권 사용 횟수를 구하는 문제이다.

문제 풀이

올-페어 최단거리를 구하면 된다.

다익스트라를 n번 돌리거나, 플로이드-워셜 알고리즘을 사용하면 된다.

해당 a->b 최단거리가 k보다 크다면 할인권을 사용하면 된다.

 

소스 코드