669. 飞行路线2
时间限制：1000 MS 内存限制：64 MB
题目描述
## 题目描述 贝茜想到一个更温暖的地方去度过这个寒冷的冬天。不幸地是,发现只有一家名叫 $AB$ 的航空公司愿意把票卖给奶牛，而且这些票的构成有些奇怪。$AB$ 拥有 $N$ 架飞机，每架都有一个特定的飞行路线，这个飞行路线包含 **2** 个或更多的城市。例如，一架飞机的路线可能是从城市 **1** 开始，然后飞到城市 **5** ，再飞到城市 **2，最后**飞到城市 **8** 。没有城市会在一条路上出现多次。如果贝茜决定使用这条路线，她可以在一条路线的任意个城市上飞机，然后在路线上任意一个城市下飞机。她不用一定在第一个城市上飞机，在最后一个城市下飞机。每条路线会有一个价格，不管贝茜沿途经过多少城市，她都要付这么多线。 贝茜想找到最近的从城市 $A$ 到城市 $B$ 的距离。由于她不想被复杂的行程图困感，她想只使用**最多两条路线**。请帮她决定她最少应该付多少钱。 ## 输入格式 第 **1** 行包含 **3** 个数字 $A$、$B$ 和 $N$。 下面的 $2N$ 行描述可用的路线，每条路线的描述占 **2**行。 上一行包含路线费用，以及沿途有少个城市(不超过**500**个)， 下一行包含 **1**个按顺序的城市的列表。 ## 输出格式 输出贝茜用一条飞行路线从城市 $A$ 飞到城市 $B$ 的最小费用,如果没有这样的路线，输出 "-1"。 ## 数据范围 对于 $20\%$ 的数据满足：$N<=5$ 对于 $40\%$ 的数据满足：$N<=7$ 村于 $100\%$ 的数括满足：$N<=10000$ ## 输入 ```in1 1 2 3 3 3 3 2 1 4 4 2 1 4 3 8 5 4 1 7 8 2 ``` ## 输出 ```out1 7 ``` ## 提示 从城市1到城市3,再用路线1从城市3到城市2。