레이팅 미적용에어 보비니아 항공은 소들이 사는 N개의 농장 (1 <= N <= 20,000)을 연결하는 항공편을 운영한다. 여느 항공사와 마찬가지로, 이 농장들 중 K개 (1 <= K <= 200, K <= N)가 허브로 지정되어 있다.
현재 에어 보비니아는 M개 (1 <= M <= 20,000)의 편도 항공편을 제공하며, 항공편 i는 농장 u_i에서 농장 v_i로 이동하고 비용은 d_i달러 (1 <= d_i <= 10,000)이다. 각 항공편에 대해 u_i와 v_i 중 적어도 하나는 허브이다. 두 농장 사이의 각 방향으로 직항편은 최대 하나이며, 출발지와 도착지가 같은 항공편은 없다.
Q개 (1 <= Q <= 50,000)의 편도 여행 요청이 접수되었으며, i번째 요청은 농장 a_i에서 농장 b_i로 가는 것이다. 각 티켓 요청이 실현 가능한지, 가능하다면 그 최소 비용을 구하시오.
출력 크기를 줄이기 위해, 실현 가능한 티켓 요청의 총 개수와 그것들의 최소 총비용만 출력해야 한다. 이 수는 32비트 정수 범위를 벗어날 수 있음에 유의한다.
첫째 줄에 정수 N, M, K, Q가 주어진다.
둘째 줄부터 M + 1번째 줄까지, i+1번째 줄에 u_i, v_i, d_i가 주어진다. (1 <= u_i, v_i <= N, u_i != v_i)
M + 2번째 줄부터 M + K + 1번째 줄까지, 각 줄에 허브 하나의 번호가 주어진다 (1..N 범위).
M + K + 2번째 줄부터 M + K + Q + 1번째 줄까지, 각 줄에 농장 a_i에서 b_i로 가는 티켓 요청을 나타내는 두 수가 주어진다. (1 <= a_i, b_i <= N, a_i != b_i)
첫째 줄에 실현 가능한 티켓 요청의 수를 출력한다.
둘째 줄에 실현 가능한 티켓 요청들을 처리하는 최소 총비용을 출력한다.
vacationgold.in · 출력을 쓸 파일 vacationgold.out3 3 1 2
1 2 10
2 3 10
2 1 5
2
1 3
3 11
20Output details: The only feasible route is 1->2->3, costing 20. There are no flights leaving farm 3.
riseoj 작성
출처 올림피아드 > USACO > 2013-2014 > December > Gold