UOJ Logo Sharp Sword 剑锋 OI

SSOI

#1038. 旅游规划travel【普及组多校联盟12】

统计

时间限制:1S / 空间限制:256MB

【问题描述】

  有n个旅游景点,编号为1到n,旅行的时间是k天,每天12小时的旅行时间,其中有m个景点是必须要游览的。有两种交通方式:公共汽车(120km/h),货车(80km/h),每个景点需要花费一定的时间。旅行的起点和终点都是1。

【输入格式】

第一行,3个整数n(1≤ n≤ 15),m(1≤ m≤n)和k(1≤ k≤100),分别表示景点的总数,必须要游览的景点的数量,总的旅游时间。
第二行,m个整数,分别表示必须要游览的景点的编号。
第三行,n个整数,分别表示各个景点的游览时间(以小时为单位)。
接下来若干行,每行4个整数,x,y,len和kind,表示景点x和y之间的一条双向边,距离是len,当kind=0表示交通工具是货车,kind=1表示交通工具是公共汽车。
当x=y=len=kind=0表示输入结束。
注:已经到过的景点,若再次经过,也要计算游览时间。特别的,最后回到景点1,不需要再次花费游览时间。

【输出格式】

一行,一个整数,表示在完成所有m个必须游览的情况下,能游览的最多景点数,否则输出"impossible"。

【输入样例1】

3 3 3
1 2 3
10 8 6
1 2 120 0
1 3 60 1
2 3 50 1
0 0 0 0

【输出样例1】

3

【输入样例2】

3 3 2
1 2 3
10 8 6
1 2 120 0
1 3 60 1
2 3 50 1
0 0 0 0

【输出样例2】

impossible