#P18783. [TOI22] 巴克欣的赏花路线

[TOI22] 巴克欣的赏花路线

巴克欣的赏花路线

有一张包含 NN 个顶点、MM 条无向边的图。顶点编号为 0,1,…,N−10,1,\ldots,N-1,边编号为 0,1,…,M−10,1,\ldots,M-1。

第 ii 条边连接 UiU_i 和 ViV_i,道路两旁有 PiP_i 棵树,通过这条边需要 TiT_i 单位时间。

巴克欣要从顶点 00 到达顶点 N−1N-1。他选择的路线必须满足:

  • 路线不能重复经过同一个顶点。
  • 若依次经过的边为 e0,e1,…,eL−1e_0,e_1,\ldots,e_{L-1},则 Pej≤Pej+1P_{e_j}\le P_{e_{j+1}} 对所有 0≤j<L−10\le j<L-1 成立。

请求出符合条件的最短总时间,并输出一条达到该时间的路线。存在多条最优路线时,输出任意一条即可。

一份输入包含多组相互独立的图。

输入格式

第一行一个整数 QQ,表示图的组数。

对于每组图:

  • 第一行两个整数 N,MN,M。
  • 接下来 MM 行,第 i+1i+1 行包含四个整数 Ui,Vi,Pi,TiU_i,V_i,P_i,T_i,描述编号为 ii 的边。

输出格式

对于每组图,输出三行:

  1. 一个整数 DD,表示最短总时间。
  2. 一个整数 LL,表示路线包含的边数。
  3. LL 个整数,依次表示经过的边的编号。

如果不存在合法路线,输出 D=0D=0、L=0L=0,第三行留空。

数据范围

  • 1≤Q≤2000001\le Q\le 200000。
  • 每组图满足 2≤N,M≤2000002\le N,M\le 200000。
  • 0≤Ui,Vi<N0\le U_i,V_i<N,1≤Pi,Ti≤1091\le P_i,T_i\le 10^9。
  • 一份输入中所有图的顶点数之和、边数之和分别不超过 200000200000。

时间限制:1 秒。内存限制:512 MB。

子任务

令 SN,SMS_N,S_M 分别表示一份输入中所有图的顶点数之和、边数之和。

子任务 分值 附加限制
1 3 每组图 N=5N=5,任意两个不同顶点之间恰好有一条边
2 8 所有边均满足 Pi=1P_i=1
3 11 SN,SM≤200S_N,S_M\le200
4 13 SN,SM≤2000S_N,S_M\le2000
5 15 所有边均满足 Pi≤100P_i\le100
6 每组图中各条边的 PiP_i 两两不同
7 35 无附加限制

每个测试点中,若所有图的最短总时间均正确,可获得该测试点的 50% 分数;若路线也全部正确,则获得全部分数。输出仍须符合格式要求。每个子任务的得分为其全部测试点得分比例的最小值乘以该子任务分值。

样例

1
5 4
0 1 1 3
1 4 2 4
2 0 4 1
4 2 3 2
7
2
0 1

样例说明

选择路线 0→1→40\to1\to4,依次经过边 0,10,1。两条边的树木数量为 1,21,2,满足非递减条件,总时间为 3+4=73+4=7。

路线 0→2→40\to2\to4 的时间虽然更短,但树木数量从 44 降为 33,不满足条件。