#P18599. Hyperloop

Hyperloop

Hyperloop

题目描述

2077年,人工智能解决了最后一个超图染色问题。失业的理论计算机科学研究者受亿万富翁 Melon Usk 委托,为他的 Hyperloop 城际交通网络编写软件。

海平面上升后,地球上只剩一座岛屿。沿岛屿海岸依次排列着 nn 座城市,编号为 1,2,…,n1,2,\ldots,n。

Melon 拥有环岛轮渡:对每个 1≤i<n1\le i<n,城市 ii 与 i+1i+1 之间有一条连接,城市 nn 与 11 之间也有连接。此外,一些不相邻的城市之间还有地下 Hyperloop 连接;隧道可以在不同深度交叉。所有连接都是双向的,任意两座城市之间至多有一条连接。

你需要寻找从城市 11 到城市 nn 的最佳路径。两种连接一视同仁:首先要求总行驶时间最短。若有多条最短路径,系统更偏爱较长的单段行程,因为乘客更可能在旅途中购买昂贵的咖啡。

精确地说,对每条候选最短路径,将其经过的全部连接的行驶时间取出(保留重复值),按非增顺序排序。应选择得到的序列字典序最大的路径。

序列 a1,…,apa_1,\ldots,a_p 字典序小于 b1,…,bqb_1,\ldots,b_q,当且仅当它是后者的真前缀,或在第一个不同的位置有 ai<bia_i<b_i。本题比较的两条路径总时间相同且边权为正,因此排序后的序列不会互为真前缀。

虽然 1,n1,n 之间已有直达轮渡,但它未必是最快的路线。请给出一条最佳路径;若有多条同样最佳的路径,输出任意一条。

输入格式

第一行一个整数 zz,表示测试用例数,1≤z≤6001\le z\le600。

每个测试用例第一行两个整数 n,mn,m,满足 3≤n≤1000003\le n\le100000、n≤m≤300000n\le m\le300000,分别表示城市数和连接总数。

接下来 mm 行,每行三个整数 ui,vi,diu_i,v_i,d_i,表示城市 ui,viu_i,v_i 之间有一条双向连接,行驶时间为 did_i。满足 1≤ui,vi≤n1\le u_i,v_i\le n、ui≠viu_i\ne v_i、1≤di≤500001\le d_i\le50000。

保证输入连接中包括 (1,2),(2,3),…,(n−1,n),(n,1)(1,2),(2,3),\ldots,(n-1,n),(n,1),任意一对城市之间至多一条连接。

所有测试用例的 nn 之和不超过 400000400000,mm 之和不超过 800000800000。

输出格式

对每个测试用例,第一行输出一个整数 kk,表示所选路径经过的城市数。

第二行输出 kk 个互不相同的城市编号,表示路径依次经过的城市。路径必须从 11 开始,在 nn 结束,并满足上文的最优性要求。

样例输入 1

2
4 6
1 2 1
1 3 2
2 3 1
2 4 2
3 4 1
1 4 4
6 11
1 2 9
2 3 12
3 4 3
4 5 5
5 6 10
6 1 22
2 4 9
3 6 1
4 6 5
2 5 2
3 5 8

样例输出 1

3
1 2 4
5
1 2 5 3 6

样例说明

第一组中最短时间为 33,有路径 1→2→41\to2\to4、1→3→41\to3\to4、1→2→3→41\to2\to3\to4。前两条的排序时间序列为 (2,1)(2,1),优于第三条的 (1,1,1)(1,1,1),因此前两条都可输出。直达路径时间为 44,不参与平局比较。

第二组的最短路径包括 1→2→5→3→61\to2\to5\to3\to6 和 1→2→5→4→3→61\to2\to5\to4\to3\to6,排序后分别为 (9,8,2,1)(9,8,2,1) 和 (9,5,3,2,1)(9,5,3,2,1),所以前一条更好。