Codeforces Round 265 (Div. 1) |
---|
Закончено |
Дан взвешенный неориентированный граф из 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. Если существует несколько кратчайших путей, выведите любой.
4 4
1 4 2
1 2 0
2 3 0
3 4 0
1 4
3
4
1 2 3 4
4 3
1 2 4
2 3 5
3 4 6
1 4
112
4
1 2 3 4
4 2
1 2 0
3 4 1
1 4
-1
Путем из вершины s в вершину t называется последовательность вершин v0, ..., vk, такая что v0 = s, vk = t, и для любого i от 0 до k - 1 вершины vi и vi + 1 соединены ребром.
Длиной пути называется сумма длин ребер между vi и vi + 1 для всех i от 0 до k - 1.
Кратчайшим путем из s в t называется путь, длина которого минимальна среди всех возможных путей из s в t.
Название |
---|