问题 L: 送外卖

问题 L: 送外卖

时间限制: 8 Sec  内存限制: 512 MB
提交: 88  解决: 17
[状态] [讨论版] [提交] [命题人:]
题目描述
在智慧岛上,程序员小 Q 每天下班都会在 n 栋公寓之间兼职送外卖。这 n 栋公寓由 m 条双向道路连通,任意两栋公寓可通过这些道路相互到达。第 i 条道路连接公寓  ui,vi,长度为 wi 米。
精通解梦的小 Q 早已在昨夜梦中知晓今日的所有订单信息:今晚,每栋公寓都恰好订了一份外卖,公寓 i 在 q秒下单。小 Q 下班后会从 1 公寓骑上他的小电驴,从 0 秒开始送餐。小 Q 可以以不超过 1 m/s的速度沿道路移动,也可以在任意位置休息不动,到达公寓后的送餐时间可以忽略不计。当然,小 Q 不能在下单前将外卖送达,以免引起客户的恐慌。
对于一笔订单,小Q在订单发起后的不同时间送达将会产生不同收益。形式化地说,对一笔订单 j,外卖平台会规定 d 个送达时间节点 qj<t1<t2<⋯<td(单位:秒),以及 d+1 个根据时间变化的收益p1, p2, ⋯, pd+1。注意,收益不一定随着送达时间推迟而减少。设小 Q 在 T 秒送达外卖,那么他的收益为

聪明的你能告诉小 Q,今晚送完所有订单最多能挣多少钱吗?


输入
第一行包含两个整数 n, m (1≤n≤14n−1≤m≤(n(n−1))/2),分别表示公寓的数量和道路的数量。
接下来 m 行,第 i 行包含三个整数  ui,vi,wi (1≤ui,vi≤nui≠vi1≤wi≤300),表示第 i 条道路连接公寓 ui,vi,长度为 wi 米。保证无重边。
接下来一行包含 n 个整数,第 i 个整数为 qi (0≤qi≤200),表示第 i 栋公寓订单的发起时刻。
接下来 3n 行,每 3 行依次描述公寓  1,2,⋯,n  订单的收益信息。第一行包含一个整数  d (1≤d≤200)。第二行包含 d 个整数,第 i 个整数为  ti (1≤ti≤200)。第三行包含 d+1 个整数,第 d+1 个整数为  pi (0≤pi≤108)。d,ti,pi的含义见题目描述。
输出
输出一行一个整数,表示最大收益。
样例输入 Copy
3 2
1 2 1
2 3 1
1 3 3
1
2
5 1
1
4
5 4
1
4
5 1
样例输出 Copy
14
提示
样例中,小 Q 在第 0 秒时已经在 1 号公寓等候订单;第 1 秒小 Q 完成 1 号订单(不计时间),获得 5 收益,随后动身前往 3 号公寓,并于第 3 秒抵达;第 3 秒小 Q 完成 3 号订单,获得 5 收益,随后动身前往 2 号公寓,并于第 4 秒抵达;第 4 秒小 Q 完成 2 号订单,获得 4 收益,此时全部订单完成,小 Q 获得最大收益 14。