(Same setup as Cow Routing.) Air Bovinia owns N planes (1 <= N <= 500), each flying on a route of two or more cities. Bessie may board at any city along a route and disembark at any later city, paying the route's full cost if she uses any part of it. She may make use of a route only once.

Bessie wants the cheapest way to travel from city A to city B, but this time she is willing to use at most two routes. Please help her decide the minimum cost she must pay.

Line 1: A, B, and N, separated by spaces.

The next 2N lines describe the available routes, two lines per route. The first line contains the cost of the route (1..1000) and the number of cities along the route (1..500). The second line lists the cities in order along the route. Each city is an integer in the range 1..10,000.

The minimum cost of an itinerary using at most two routes to travel from city A to city B. If there is no such solution, output -1.

riseoj 작성

출처 올림피아드 > USACO > 2014-2015 > January > Bronze