레이팅 미적용추운 겨울 날씨에 지친 소 베시는 휴가를 위해 더 따뜻한 곳으로 비행기를 타고 떠날 계획이다. 소에게 표를 팔려는 항공사는 Air Bovinia 하나뿐이다.
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 28Output details: Only route 3 connects city 1 to city 2 in a single route, at a cost of 8.
riseoj 작성
출처 올림피아드 > USACO > 2014-2015 > January > Bronze