여행 > 문제은행



실전대비 Level6

1517 : 여행

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 9 회    시도횟수: 37 회   



정올국은 N개의 섬으로 이루어져 있고 그중 K개의 섬에서 세관신고를 할 수 있다. 행정상 편의를 위해 섬들의 코드를 1~N으로 매겨놓고, 세관신고가 가능한 섬들의 코드는 1~K로 지정해 놓았다.

 

정올국의 N개의 섬에는 공항이 있어서 비행기를 타고 다른 섬으로 갈 수 있다. 정올국의 해양기후가 매우 안 좋기 때문에 오직 비행기로만 섬 사이를 이동할 수 있다.

 

정올국에는 총 M개의 여행사가 있고 각 여행사는 Pi의 요금을 내고 Di번 섬에서 Ai번 섬으로 가는 편도 여행을 제공한다.

 

주찬이는 여행을 계획하는 Q명의 사람들에 대해서 S번 섬에서 E번 섬으로 가는 데 드는 최소비용을 구해야 한다. 같은 섬을 여러 번 들러도 되지만, 생태계를 보호하고 테러를 방지하기 위해 여행 도중에 세관신고를 반드시 해야 한다. 이러다 보니, S번 섬에서 E번 섬으로 가는 것이 아예 불가능할 수도 있다.

 

모든 여행의 요청을 받으면, 그중 가능한 경로의 수와 최소비용의 합을 구하는 프로그램을 작성하여라.




첫 번째 줄에는 섬의 수 N, 여행사의 수 M, 세관신고를 할 수 있는 섬의 수 K, 여행 요청의 수 Q가 주어진다. (1 ≤ N ≤ 200, 1 ≤ M ≤ 10,000, 1 ≤ K ≤ min(N,100), 1 ≤ Q ≤ 10,000)

두 번째 줄부터 M개의 줄에는 각 여행사의 출발 섬 Di, 도착 섬 Ai와 요금 Pi가 주어진다.
(1 ≤ Di, Ai ≤ N, 1 ≤ Pi ≤ 1,000,000)

그 다음 줄부터 Q개의 줄에는 각 사람의 출발 섬 S, 도착 섬 E가 주어진다. (1 ≤ S, E ≤ N)



첫 번째 줄에는 가능한 경로의 수를 출력한다.두 번째 줄에는 최소비용의 합을 출력한다.


3 3 1 3
3 1 10
1 3 10
1 2 7
3 2
2 3
1 2
2
24


첫 번째 여행 : 3->1->2로 가면 17의 비용으로 여행할 수 있다.
두 번째 여행 : 2번 섬에서 출발하는 여행사가 없기 때문에 여행할 수 없다.
세 번째 여행 : 1->2로 가면 7의 비용으로 여행할 수 있다.






HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.