|
Дейкстра за O(M log N)
(Время: 3 сек. Память: 128 Мб Сложность: 60%)
Напишите программу, которая будет находить расстояния в неориентированном взвешенном графе с неотрицательными длинами ребер, от указанной вершины до всех остальных. Программа должна работать быстро для больших разреженных графов.
Входные данные
Первая строка входного файла INPUT.TXT содержит три числа N, M и S – количество вершин, количество ребер и стартовая вершина графа соответственно (1 ≤ N ≤ 60 000, 1 ≤ M ≤ 200 000, 0 ≤ S < N). Вершины в графе нумеруются с 0 до N-1. Далее следуют M строк, каждая из которых содержит по три целых числа. Первые два из них в пределах от 0 до N-1 обозначают концы соответствующего ребра, третье – в пределах от 0 до 20 000 обозначает длину этого ребра.
Выходные данные
В выходной файл OUTPUT.TXT выведите N целых чисел – кратчайшие расстояния от вершины с номером S до 0-й, 1-й, 2-й и т.д вершин. Если некоторая вершина недостижима, вместо расстояния выводите число 2009000999 (гарантировано, что все реальные расстояния меньше).
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 5 7 1
1 2 5
1 3 2
2 3 4
2 4 3
3 4 6
0 3 20
0 4 10 | 18 0 5 2 8 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
