Problem 1056. -- 旅游安排

1056: 旅游安排

Time Limit: 2 Sec  Memory Limit: 64 MB
Submit: 9  Solved: 1
[Submit][Status][Web Board]

Description

卿爷和雯君正在安排一次市内旅游,旅游景点包括吴江路小吃街、南京路步行街、野生动物园、城隍庙、七宝街、福州路、新天地等若干经典去处。很快卿爷就发现,这些景点比较分散,从一个地方到另一个地方可能要花费比较长的时间,这样玩起来会很累。比如如果要你从野生动物园玩完后就去七宝街玩,你会立刻吟唱起草原上泥潭里一匹马的歌曲 。为了让自己和心爱的人能够开开心心的游玩,卿爷决定规划一下游玩路线。
事实上,卿爷和雯君对每个游玩景点都有一个评价,表示对这个景点的喜好程度。这个景点的喜好程度和他俩到达这个景点的疲惫程度的差值将是他俩在这个景点游玩的满意程度。疲惫程度和到达这个景点的路程相关。卿爷希望,他俩对所有景点的满意程度之和能够最大。卿爷和雯君将从赤峰路校门口出发,不重复的游览全部景点。现在就请你来帮卿爷规划一下旅游线路吧!

Input

第1行,N、M、D三个正整数,表示有N个景点,M条道路相连,每走D单位的路程将给卿爷和雯君增加1单位的疲惫度。
第2行,N个正整数,表示卿爷和雯君对每个景点的喜好值。
第3行,N个正整数,表示从出发点到各个景点的距离。
第4到M+3行,每行A、B、C三个正整数,表示景点A和景点B之间有一条长度为C的互连道路。
1<=N<=10,1<=C, D<=1000,景点从1到N编号。

Output

第一行,总的满意值,保留到小数点后两位。
第二行,最佳旅游线路,为景点编号,以空格隔开。如果有多解,输出字典序最小的方案。数据保证有解。

Sample Input

5 5 1
5 3 3 8 10
1 1 1 1 1
1 2 8
2 3 2
2 4 1
1 5 2
3 5 3

Sample Output

6.00
4 2 3 5 1

HINT

Source

[Submit][Status]