레이팅 미적용(Bronze의 소의 여행 경로 문제들과 설정이 같다.) Air Bovinia는 N대의 비행기를 보유하고 있으며 (1 <= N <= 1000), 각 비행기는 두 개 이상의 도시로 이루어진 노선을 운항한다. 베시는 노선 위의 아무 도시에서나 탑승해 그보다 뒤에 있는 아무 도시에서나 내릴 수 있으며, 노선의 일부라도 이용할 때마다 그 노선의 비용을 전부 지불해야 한다 (같은 노선을 여러 번 이용하면 이용할 때마다 비용을 낸다).
베시는 도시 A에서 도시 B까지 가장 저렴하게 이동하는 방법과, 그 최소 비용을 달성하기 위해 타야 하는 개별 항공편 수의 최솟값을 알고 싶다.
첫째 줄에 A, B, N이 공백으로 구분되어 주어진다.
다음 2N개의 줄에 걸쳐 이용 가능한 노선들이 노선당 두 줄씩 주어진다. 첫 번째 줄에는 노선의 비용 (1..1,000,000,000)과 노선에 포함된 도시의 수 (1..100)가 주어진다. 두 번째 줄에는 도시들이 순서대로 나열된다. 각 도시는 1..1000 범위의 정수이다. 총 비용이 32비트 정수 범위를 넘을 수 있으므로 64비트 정수를 사용해야 한다.
도시 A에서 도시 B로 가는 여정의 최소 비용과, 그 최소 비용을 달성하는 데 필요한 개별 항공편 수의 최솟값을 출력한다. 해가 없으면 "-1 -1"을 출력한다.
cowroute.in · 출력을 쓸 파일 cowroute.out3 4 3
3 5
1 2 3 4 5
2 3
3 5 4
1 2
1 52 2riseoj 작성
출처 올림피아드 > USACO > 2014-2015 > January > Silver