比赛场次 253
比赛名称 20150408
比赛状态 已结束比赛成绩
开始时间 2015-04-08 19:00:00
结束时间 2015-04-08 22:00:00
开放分组 全部用户
注释介绍
题目名称 牛的路线2
输入输出 cowrouteb.in/out
时间限制 1000 ms (1 s)
内存限制 256 MiB
测试点数 10 简单对比
用户 结果 时间 内存 得分
Gravatarcstdio AAAAAWEEEE 0.355 s 4.22 MiB 50
GravatarTA AAAAAWETEE 1.646 s 103.39 MiB 50
GravatarAsm.Def AAAAWWTTTT 4.008 s 39.67 MiB 40
GravatarKZNS AAAEEEEEEE 0.533 s 0.32 MiB 30
Gravatar水中音 WAAWWWWWWW 0.074 s 1.67 MiB 20
Gravatarok WWWAWWWWWW 0.001 s 0.29 MiB 10
GravatarSatoshi WWWAWWWWWW 0.004 s 0.31 MiB 10
Gravatarwolf. WWWAWWWWWW 0.004 s 0.43 MiB 10
GravatarRa-xp WWWAWWWWWW 0.004 s 39.26 MiB 10

牛的路线2

★★   输入文件:cowrouteb.in   输出文件:cowrouteb.out   简单对比
时间限制:1 s   内存限制:256 MiB

【题目描述】


农场冬天寒冷的天气令人厌倦,贝茜奶牛计划飞到一个温暖的目的地度假。不幸的是,她发现只有一家航空公司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。


【来源】

在此键入。