레이팅 미적용(소의 여행 경로 문제와 설정이 같다.) Air Bovinia는 N대의 비행기를 보유하고 있으며 (1 <= N <= 500), 각 비행기는 두 개 이상의 도시로 이루어진 노선을 운항한다. 베시는 노선 위의 아무 도시에서나 탑승해 그보다 뒤에 있는 아무 도시에서나 내릴 수 있으며, 노선의 일부라도 이용하면 그 노선의 비용을 전부 지불해야 한다. 각 노선은 한 번만 이용할 수 있다.
베시는 도시 A에서 도시 B까지 가장 저렴하게 이동하고 싶은데, 이번에는 노선을 최대 두 개까지 이용할 의향이 있다. 베시가 지불해야 하는 최소 비용을 구하시오.
첫째 줄에 A, B, N이 공백으로 구분되어 주어진다.
다음 2N개의 줄에 걸쳐 이용 가능한 노선들이 노선당 두 줄씩 주어진다. 첫 번째 줄에는 노선의 비용 (1..1000)과 노선에 포함된 도시의 수 (1..500)가 주어진다. 두 번째 줄에는 노선을 따라 지나는 도시들이 순서대로 나열된다. 각 도시는 1..10,000 범위의 정수이다.
최대 두 개의 노선을 이용해 도시 A에서 도시 B로 이동하는 여정의 최소 비용을 출력한다. 그러한 방법이 없으면 -1을 출력한다.
cowroute.in · 출력을 쓸 파일 cowroute.out1 2 3
3 3
3 2 1
4 4
2 1 4 3
8 5
4 1 7 8 27Output details: Use route 2 (city 1 to city 3) then route 1 (city 3 to city 2), total cost 4+3=7.
riseoj 작성
출처 올림피아드 > USACO > 2014-2015 > January > Bronze