← 返回题目列表

Codeforces · 464/E

E. 经典问题

中文机器翻译题面 查看原题

给定一个有 n 个顶点和 m 个边的加权无向图。找到从顶点 s 到顶点 t 的最短路径,否则说明该路径不存在。

输入

输入的第一行包含两个空格分隔的整数 — n 和 m (1 ≤ n ≤ 105;0 ≤ m ≤ 105)。

接下来的 m 行包含图边的描述。第 i 行包含三个以空格分隔的整数 — ui、vi、xi (1 ≤ ui, vi ≤ n; 0 ≤ xi ≤ 105)。这意味着编号为 ui 和 vi 的顶点通过长度为 2xi(2 的 xi 次方)的边连接。

最后一行包含两个空格分隔的整数 - 顶点 s 和 t 的数量。

顶点编号为 1 到 n。该图不包含重边和自环。

输出

在第一行中,如果路径存在,则打印最短路径的长度除以 1000000007 (109 + 7) 后的余数,如果路径不存在,则打印 -1。

如果路径存在则在第二行打印整数 k — 从顶点 s 到顶点 t 的最短路径中的顶点数;第三行打印 k 个空格分隔的整数——访问顺序中最短路径的顶点。第一个顶点应该是顶点 s,最后一个顶点应该是顶点 t。如果有多个最短路径,则打印其中任意一个。

示例

输入 #1

4 4
1 4 2
1 2 0
2 3 0
3 4 0
1 4

输出 #1

3
4
1 2 3 4

输入 #2

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

输出 #2

112
4
1 2 3 4

输入 #3

4 2
1 2 0
3 4 1
1 4

输出 #3

-1

注意

从顶点 s 到顶点 t 的路径是序列 v0, ..., vk,使得 v0 = s, vk = t,并且对于从 0 到 k - 1 的任何 i,顶点 vi 和 vi + 1 通过边连接。

路径的长度是对于从 0 到 k - 1 的所有 i,vi 和 vi + 1 之间的边的权重之和。

从s到t的最短路径是从s到t的所有可能路径中长度最小的路径。