在一座未来城市中，一个高度自动化的无人机物流网络负责着全城的包裹配送。 这个网络由 个配送站 组成。 无人机可以在这些配送站之间沿着预设的空中走廊进行飞行。 每条空中走廊连接两个配送站，并且是双向通行的。 由于距离、风阻等因素，无人机飞过每条走廊都需要消耗一定的能量，记为 。 这个能耗是固定的，且双向飞行的能耗相同 ()。 当一个配送任务下达时，系统需要从起始站 规划出一条到达目的站 的、总能耗最低的飞行路径。 无人机的导航系统遵循最短路径原则。对于一个从 到 的任务，系统会计算出一条或多条总能耗最低的路径。 无人机从起始站出发的第一站被称为下一跳。由于可能存在多条能耗并列最低的路径，因此下一跳也可能不止一个。 您的任务是：给定整个物流网络的布局和各条走廊的能耗，并指定起始站和目的站，计算出： 1. 完成该配送任务所需的最低总能耗。 2. 无人机从起始站出发的所有可能的下一跳站点的集合。
输入描述:
第一行包含两个整数 和 ，分别代表配送站的总数和空中走廊的数量。接下来的 行描述了空中走廊的信息。每行包含三个正整数 ，分别代表这条走廊连接的两个配送站的编号 和飞行所需的能耗 。站点编号 的范围在 内。最后一行包含两个正整数 和 ，代表任务的起始站和目的站。
输出描述:
输出共两行：第一行为一个整数，表示从 到 的最低总能耗。第二行为一个或多个正整数，代表所有可能的下一跳站点的编号。请将这些编号按升序排列，并用单个空格分隔。特殊情况：1. 如果目的站 无法从起始站 到达，则最低能耗输出 `-1`，下一跳集合也输出 `-1`。2. 如果起始站与目的站相同 ()，则最低能耗为 `0`，下一跳集合输出 `-1`。
示例1
输入
19 71
7 9 98
9 14 98
6 11 27
2 10 8
6 8 2
10 11 68
16 17 34
2 13 29
13 18 70
5 7 46
1 5 76
5 12 96
5 17 18
11 16 91
3 18 45
8 10 76
7 13 20
2 9 21
8 12 96
7 10 37
6 16 45
15 19 32
4 11 15
2 6 46
7 11 32
6 13 38
9 18 44
8 14 42
18 19 80
4 7 75
6 9 51
9 12 64
10 13 26
1 13 10
10 15 69
10 19 69
2 19 16
11 12 24
17 19 15
13 17 48
13 16 84
3 11 31
1 9 10
15 16 49
3 8 69
7 8 31
4 15 96
5 8 45
9 10 12
9 16 78
10 17 20
5 18 5
8 17 39
5 6 48
4 16 40
14 16 15
13 15 65
10 16 43
12 18 74
1 14 83
1 10 18
2 5 55
12 16 41
4 18 13
5 16 59
9 13 14
4 8 2
4 12 45
14 18 97
12 17 17
4 13 40
16 18
备注:
本题由牛友@Charles 整理上传
加载中...