ez_code   4년 전

문제

농장의 추운 날씨에 지쳐, 소 베시는 따뜻한 지역으로 여행을 떠나기로 했습니다. 안타깝게도 보비니아 항공사만이 소를 위한 비행기 표를 판매하는데, 비행기 표가 구조적으로 다소 복잡합니다.

보비니아 항공사는 N개의 비행기를 소유하고 있는데 (1 <= N <= 500), 각 비행기는 두 개 이상의 도시로 이루어진 특정 노선을 운행합니다. 예를 들어, 한 비행기는 도시 1에서 노선을 시작해 도시 5, 도시 2로 날아갔다가 도시 8로 도착합니다. 노선에서 한 도시를 여러 번 들르지는 않습니다. 베시가 노선을 사용하기로 결정한다면, 베시는 노선의 어느 도시에서도 탑승 가능하며 노선을 따라가다 어느 도시에서도 내릴 수 있습니다. 첫 번째 도시에서 탑승하거나 마지막 도시에서 내릴 필요가 없습니다. 각 노선에는 비용이 있고, 노선을 이용하는 동안 들른 도시의 수와는 관계 없이 베시는 노선의 일부를 이용할 경우 그 비용을 내야 합니다.

베시는 (도시 A에 있는) 농장에서 (도시 B가 있는) 열대 지역으로 여행하는 가장 싼 방법을 찾으려고 합니다. 복잡한 여행 일정 때문에 혼란을 겪기는 싫으므로, 베시는 딱 하나의 노선만 이용할 것입니다. 그녀가 지불해야 하는 최소 비용을 계산해 베시를 도와줍시다.

입력

첫 줄에 A, B, N이 공백으로 구분되어 주어집니다.

다음 2N개의 줄에 가능한 노선이, 두 줄에 하나씩 주어집니다. 첫 줄에는 (1 이상 1000 이하의 정수인) 노선 비용과, (1 이상 500 이하인) 노선에 있는 도시의 수가 주어집니다. 둘째 줄에는 노선에서 들르는 도시가 순서대로 주어집니다. 각 도시는 1 이상 10000 이하의 정수로 구별합니다.

출력

 베시가 도시 A에서 도시 B로 이동할 때 사용할 수 있는 노선 하나의 최소 비용을 출력합니다. 그런 노선이 없을 경우, -1을 출력합니다. 

댓글을 작성하려면 로그인해야 합니다.