P6822: 奶牛航线I
传统题
1.000s
时间限制
256MB
内存限制
9 提交
1 解决
【题目描述】
【题目描述】
奶牛贝西厌倦了农场冬天的寒冷天气，打算离开农场飞到一个温暖的目的地度假。不幸的是,
她发现只有一家航空公司，即Bovinia航空公司愿意出售奶牛的票，这些票有点复杂结构。
Bovinia
航空公司拥有N架飞机(1 <= N <= 500)，每架飞机的航线
由两个或多个城市组成的特定“路线”。例如，一个飞机可能会在1号城市出发，然后飞往城市5
，然后飞往城市2，最后飞往城市8。没有城市在一条航线
中出现多次。如果贝西选择使用她可以在沿途的任何城市登机
，然后在沿途的任何城市。她不需要在第一个城市或在最后一个城市下飞机
。每条路线都有费用，如果贝西使用路线的任何部分，她必须支付，她都必须支付这笔费用。 不管她沿途去过多少个城市。贝西想从她的农场找到最便宜的旅行方式（在城市A
）前往她的度假
目的地（城市B
）。因为她不
想要被复杂的行程所迷惑，她只想使
用一条路线。请帮她决定她必须支付的最低费用是多少。
【
输入格式】:(cowroute.in)
第一行输入包含A
、B和N，用空格分隔。
接下来的2N
行描述可用的航线
，每两行为一个路
线。第一行包含使用路线
的开销(
一个整数范围为1..1000)，以及沿线城市的数量(1..500范围内的整数)。沿线城市按顺序排列
。每个城市由一个1..10,000
范围内的整数。
【
输出格式】:(cowroute.out)
输出贝西可以使用的单路线的最低成本
如果没有，则输出-1
。
【
样例输入】:
1 2 3
3 3
3 2 1
4 4
2 1 4 3
8 5
4 1 7 8 2
【
样例输出】:
8
【样例说明】
解决方案指出:
虽然有一个更便宜的双路线解决方案(
使用2号路线旅行 从1号城市到3号城市，然后从3号城市到2号城市， 贝西只被允许走一条路线，所以她必须走3号路 代价是8。