(Same setup as the Bronze Cow Routing problems.) Air Bovinia owns N planes (1 <= N <= 1000), 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 each time she uses any part of it (using a route multiple times costs for each use).

Bessie wants the cheapest way to travel from city A to city B, and also the smallest number of individual flights she must take to achieve this minimum cost.

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..1,000,000,000) and the number of cities along the route (1..100). The second line lists the cities in order. Each city is an integer in the range 1..1000. The total cost may exceed a 32-bit integer, so use 64-bit integers.

The minimum cost of an itinerary from city A to city B, as well as the minimum number of individual flights required to achieve this minimum cost. If there is no solution, output "-1 -1".

riseoj 작성

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