Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Дейкстра за O(M log N)

(Время: 3 сек. Память: 32 Мб Сложность: 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.TXTOUTPUT.TXT
15 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

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Введение
 Целочисленная арифметика
 Алгоритмы сортировки
 Длинная арифметика
 C++ Standard Template Library
 Динамическое программирование
 Комбинаторика
 Вычислительная геометрия
 Строки
 Структуры данных
 Теория графов - 1
 Теория графов - 2
 Алгоритм Флойда
 Алгоритм Форда-Беллмана
 Алгоритм Дейкстры
 Минимальный каркас
 Эйлеров цикл, конденсация
 Паросочетания
 A. Алгоритм Дейкстры
 B. Алгоритм Дейкстры - 2
 C. Дейкстра за O(M log N)
 D. Заправки
 E. Автобусы
 F. Транспортировка
 G. Химическая тревога
 H. Защищенное соединение

Красноярский краевой Дворец пионеров, (c)2006 - 2019, E-mail: admin@acmp.ru