#LUOGUP4453. 寻宝

寻宝

题目背景

Steve成功打开了机关,发现机关后是一个巨大的迷宫

题目描述

这个迷宫一共有nn个洞穴,洞穴之间有很多单向隧道,很难数清

但经过分析,发现:

这些隧道可以分为mm组,对于每一组,编号在区间[sl,sr][s_l,s_r]内的每一个洞穴,与编号在区间[tl,tr][t_l,t_r]内的每一个洞穴之间,都有一条隧道,每组内共有(srsl+1)(trtl+1)(s_r-s_l+1)\cdot (t_r-t_l+1)条隧道,通过同组内每一条隧道的时间都相等

为了进一步节约时间,Steve可以挖掘新的隧道

但是,每个洞穴的性质不同,导致挖掘隧道的难度不同,有些洞穴甚至无法挖掘隧道

具体来说,第ii个洞穴有一个值viv_ivi=0v_i=0表示无法挖掘隧道,对于其它值,表示从第ii个洞穴开始,挖掘一条到第jj个洞穴的隧道,并到达第jj个隧道,需要花费ijvi|i-j|*v_i时间

Steve希望在最短时间内到达第nn个洞穴,决定不限制挖掘隧道的数量

现在,你需要告诉Steve最少需要用的时间

如果可能,你应帮助Steve求出一种最优方案

输入格式

第一行两个整数n,mn,m

接下来一行nn个整数v1,v2,...,vnv_1,v_2,...,v_n

接下来mm行,每行描述一组隧道

每行55个整数sl,sr,tl,tr,ws_l,s_r,t_l,t_r,w,其中ww表示通过时间

输出格式

如果无解,则只需输出一行一个整数"-1"(不含引号)

如果有解,则按下列格式输出:

第一行一个整数tt,表示最少花费的时间

如果你无法给出方案,在第二行输出一个整数00

如果你可以给出方案,在第二行输出一个整数cc,在第三行输出cc个整数,依次表示一种最优方案经过的洞穴编号

你并不需要告诉Steve经过的隧道是否为挖掘出来的,或者属于哪一组

6 2
0 1 2 0 0 0
1 1 2 3 5
4 5 6 6 2

9
3
1 2 6
6 2
0 1 2 0 0 0
1 1 2 3 5
4 5 6 6 2

9
4
1 3 4 6

提示

样例1:1号到2号走第一组隧道,2号到6号挖掘隧道,用时1(62)=41*(6-2)=4

样例2:1号到3号走第一组隧道,3号到4号挖掘隧道,用时2(43)=22*(4-3)=2,4号到6号走第二组隧道

每个Subtask包括两个测试点,取较低分

对于每个测试点:

如果输出格式错误,那么,该测试点得0分

如果你没有给出正确的用时,那么,该测试点得0分

如果你给出正确的用时,但没有给出方案,那么你可以得到该测试点一半的分数(每个测试点得分向下取整)

如果你给出了错误方案,那么你可能可以得到该测试点一半的分数,或者得0分

如果你给出了正确的方案,那么你可以得到该测试点全部的分数

上面两个输出都可以得到满分,还有一种方案是12461 2 4 6

如果你输出:

9
0

那么你可以得到该测试点一半的分数

数据范围:

1w,vi1091\le w,v_i \le 10^9

Subtask 分值 n m 特殊性质
1 5 100
2 10 3000
3 11 50000 50000 2,3
4 10 1
5 12 0
6 1
7 13 20 3
8
9 14 50000

特殊性质1:所有vi=0v_i=0

特殊性质2:所有vi{0,k}v_i \in \{0,k\}kk为常数

特殊性质3:所有sl=sr,tl=trs_l=s_r,t_l=t_r

保证存在到达nn号洞穴的方案

关于输出错误方案:

如果输出的2cn2\leq c\leq n,经过的点以11开头,以nn结尾,且中间的点都是在(1,n)(1,n)的整数,则这组解可能是一组最优解,可以得到一半分数

否则,得0分

不用担心spj会TLE/MLE