Cow Routing (Silver)#11190
Tired of the cold winter weather on her farm, Bessie the cow plans to fly to a warmer destination for a vacation. Unfortunately, she discovers that only one airline, Air Bovinia, is willing to sell tickets to cows, and that these tickets are somewhat complicated.
Air Bovinia owns planes, each of which flies along a specific "route" consisting of two or more cities. For example, one plane might fly along a route that starts in city , then flies to city , then to city , and finally to city . No city appears more than once on a route.
If Bessie chooses to use a route, she can board the plane at any city along the route and then disembark at any city that appears later on the route. She does not need to board at the first city or disembark at the last city. Each route has a fixed cost, which Bessie must pay whenever she uses any part of that route, regardless of how many cities she visits along it.
If Bessie uses the same route multiple times during her journey (that is, if she leaves the route and later returns to use it again from another city), she must pay the route's cost each time she uses it.
Bessie wants to find the cheapest way to travel from her farm, located in city , to her tropical destination, located in city . Please help her determine both the minimum total cost and, among all itineraries with this minimum cost, the minimum number of individual flights she must take.
The first line contains , and n~(1 \le n \le 1000).
The next lines describe the available routes, with two lines per route. The first line contains the cost of using the route (an integer in the range 1 \ldots 10^9) and the number of cities along the route (an integer in the range ). The second line contains a list of the cities in the order in which they appear along the route. Each city is identified by an integer in the range .
Note that the total cost of an itinerary can easily exceed the range of a 32-bit integer, so you should use 64-bit integers (for example, 'long long' in C/C++).
Output the minimum cost of an itinerary that allows Bessie to travel from city to city , followed by the minimum number of individual flights among all itineraries with that minimum cost.
If no solution exists, print "-1 -1" (quotes for clarity) on a single line.
Example 1