레이팅 미적용에어 보비니아 항공은 소들이 사는 N개의 농장 (1 <= N <= 200)을 연결하려고 계획하고 있다. 여느 항공사와 마찬가지로, 이 농장들 중 K개 (1 <= K <= 100, K <= N)가 허브로 선정되었다. 농장에는 편의상 1..N의 번호가 붙어 있으며, 농장 1..K가 허브이다.
현재 이 농장들을 연결하는 M개 (1 <= M <= 10,000)의 편도 항공편이 있다. 항공편 i는 농장 u_i에서 농장 v_i로 이동하며, 비용은 d_i달러 (1 <= d_i <= 1,000,000)이다.
항공사는 Q개 (1 <= Q <= 10,000)의 편도 여행 요청을 받았다. i번째 여행은 농장 a_i에서 농장 b_i로 가는 것이다. a_i에서 b_i로 가기 위해, 여행은 직항편들의 임의의 나열을 포함할 수 있고 (같은 농장을 여러 번 방문해도 된다), 반드시 허브를 적어도 하나 거쳐야 한다 (허브가 출발지나 목적지여도 되고 아니어도 된다). 이 때문에 유효한 경로가 존재하지 않을 수도 있다. 유효한 경로가 존재하는 여행 요청들에 대해서는 유효한 경로의 최소 비용을 구하는 것이 목표이다.
첫째 줄에 네 정수 N, M, K, Q가 주어진다.
둘째 줄부터 1+M번째 줄까지, i+1번째 줄에 항공편 i의 u_i, v_i, d_i가 주어진다.
2+M번째 줄부터 1+M+Q번째 줄까지, 1+M+i번째 줄에 i번째 여행을 나타내는 a_i와 b_i가 주어진다.
첫째 줄에 (Q개 중) 유효한 경로가 가능한 여행의 수를 출력한다.
둘째 줄에 유효한 경로가 가능한 모든 여행에 대해, 가능한 최소 경로 비용의 합을 출력한다.
vacation.in · 출력을 쓸 파일 vacation.out3 3 1 3
3 1 10
1 3 10
1 2 7
3 2
2 3
1 22
24Output details: Trip 3->2 costs 10+7; trip 2->3 has no route; trip 1->2 costs 7. Two valid trips, total 24.
riseoj 작성
출처 올림피아드 > USACO > 2013-2014 > December > Silver