Processing math: 100%

Задача D. Быстрый Дейкстра

Автор:StdAlg   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Вам необходимо написать программу, которая получает взвешенный ориентированный граф и находит в нем расстояния от вершины S до всех остальных вершин. Расстояние от вершины S до некоторой вершины W — это минимальная длина пути из S в W. Длина пути — это сумма весов всех рёбер, входящих в него.

Формат входного файла

Входной файл содержит три числа N, M и S. Вершины занумерованы целыми числами от 1 до N. S — это номер начальной вершины. M — это количество рёбер. Каждая из следующих M строк содержит три числа — номера начальной и конечной вершин текущего ребра и его вес соответственно. Все веса положительны. Между двумя вершинами может быть максимум одно ребро в каждом направлении.

Формат выходного файла

Выходной файл должен содержать N чисел. Каждое I-е число — это расстояние от вершины до S до вершины I. Если некоторые вершины недостижимы из S, то для для них должно быть выведено 1.

Ограничения

1N,M100000 Все веса меньше или равны 1000.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
5 3 1
1 2 5
1 3 7
3 4 10
0 5 7 17 -1

0.069s 0.015s 15