#P18599. Hyperloop
Hyperloop
Hyperloop
题目描述
2077年,人工智能解决了最后一个超图染色问题。失业的理论计算机科学研究者受亿万富翁 Melon Usk 委托,为他的 Hyperloop 城际交通网络编写软件。
海平面上升后,地球上只剩一座岛屿。沿岛屿海岸依次排列着 座城市,编号为 。
Melon 拥有环岛轮渡:对每个 ,城市 与 之间有一条连接,城市 与 之间也有连接。此外,一些不相邻的城市之间还有地下 Hyperloop 连接;隧道可以在不同深度交叉。所有连接都是双向的,任意两座城市之间至多有一条连接。
你需要寻找从城市 到城市 的最佳路径。两种连接一视同仁:首先要求总行驶时间最短。若有多条最短路径,系统更偏爱较长的单段行程,因为乘客更可能在旅途中购买昂贵的咖啡。
精确地说,对每条候选最短路径,将其经过的全部连接的行驶时间取出(保留重复值),按非增顺序排序。应选择得到的序列字典序最大的路径。
序列 字典序小于 ,当且仅当它是后者的真前缀,或在第一个不同的位置有 。本题比较的两条路径总时间相同且边权为正,因此排序后的序列不会互为真前缀。
虽然 之间已有直达轮渡,但它未必是最快的路线。请给出一条最佳路径;若有多条同样最佳的路径,输出任意一条。
输入格式
第一行一个整数 ,表示测试用例数,。
每个测试用例第一行两个整数 ,满足 、,分别表示城市数和连接总数。
接下来 行,每行三个整数 ,表示城市 之间有一条双向连接,行驶时间为 。满足 、、。
保证输入连接中包括 ,任意一对城市之间至多一条连接。
所有测试用例的 之和不超过 , 之和不超过 。
输出格式
对每个测试用例,第一行输出一个整数 ,表示所选路径经过的城市数。
第二行输出 个互不相同的城市编号,表示路径依次经过的城市。路径必须从 开始,在 结束,并满足上文的最优性要求。
样例输入 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
样例说明
第一组中最短时间为 ,有路径 、、。前两条的排序时间序列为 ,优于第三条的 ,因此前两条都可输出。直达路径时间为 ,不参与平局比较。
第二组的最短路径包括 和 ,排序后分别为 和 ,所以前一条更好。