1927. [USACO Jan15] 牛的路线2

【题目描述】

农场冬天寒冷的天气令人厌倦，贝茜奶牛计划飞到一个温暖的目的地度假。不幸的是，她发现只有一家航空公司bovinia，愿意给牛出售门票，这些票结构上有点复杂。

bovinia航空公司拥有N架飞机（1≤N≤500），其中每架飞机有一个具体的"航线"，连接两个或两个以上的城市。例如，一个飞机的可能飞行路线，开始在城市1，然后飞到城市5，然后飞到城市2，最后飞到城市8。没有城市在航线中出现多次。如果她选择使用一个路线，她可以在沿途的任何城市下来，也可以在路线中后面的沿线城市再次上飞机。她不需要在第一个城市下飞机，也不需要在最后的城市上飞机。每条航线具有一定的费用，如果她采用路线的任何部分，贝茜必须支付成本，可以不考虑她走访沿线城市数量。一条路线贝茜只可以使用一次（即，她不能使用一条路线并且随后使用相同的路线的不同部分）。

贝茜想要找到从她的农场（城市A）到目的地（城市B）的最便宜旅行方式。因为她不想被复杂的换乘困扰，她希望至多使用两条路线。请帮助她计算必须支付的最小代价。

[注意，这道题和上一题的唯一区别是这里贝茜可以使用两条路线，但在上一题中只能使用一条]

【输入格式】

输入的第一行包含A，B，N，用空格隔开。

  接下来2N行描述了可用的路线，每条路线有两行。第一行包含使用路线的成本（一个整数,范围1..1000），与沿线城市的数量（一个范围在1..500的整数）。第二行包含一个列表的沿线为城市。每个城市都是确定的整数,范围是1..10000。

【输出格式】

输出一个整数，表示路茜从城市A到城市B旅行的最低成本，如果没有这样的路线，输出-1。

【样例输入】

1 2 3
3 3
3 2 1
4 4
2 1 4 3
8 5
4 1 7 8 2

【样例输出】

7

【提示】

样例解释：

使用路2从城市1到城市3，然后使用路线1从城市3到城市2。

【来源】

在此键入。