e-olymp
favorite Saytın davamlılığını təmin etmək üçün sizin köməyinizə ehtiyacımız vardır, ətrafli məlumat üçün bannerə klikləyin
Yarışlar

Dijkstra algorithm

Кратчайший путь

Дан неориентированный взвешенный граф. Найти кратчайший путь между двумя данными вершинами.

Входные данные

Первая строка содержит натуральные числа n и m (n2000, m50000) - количество вершин и рёбер графа. Вторая строка содержит натуральные числа s и f (1s, fn, sf) - номера вершин, длину пути между которыми требуется найти. Следующие m строк содержат по три числа bi, ei и wi - номера концов i-ого ребра и его вес соответственно (1bi, ein, 0wi100000).

Выходные данные

Первая строка должна содержать одно число - длину минимального пути между вершинами s и f. Во второй строке через пробел выведите вершины на кратчайшем пути из s в f в порядке обхода. Если путь из s в f не существует, выведите -1.

prb4856.gif

Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
4 4
1 3
1 2 1
2 3 2
3 4 5
4 1 4
Çıxış verilənləri #1
3
1 2 3