Задача A. Быстрый Дейкстра
Условие
Вам необходимо написать программу, которая получает взвешенный ориентированный
граф и находит в нем расстояния от вершины
S до всех остальных вершин.
Расстояние от вершины
S до некоторой вершины
W — это минимальная длина пути
из
S в
W. Длина пути — это сумма весов всех рёбер, входящих в него.
Формат входного файла
Входной файл содержит три числа
N,
M и
S.
Вершины занумерованы целыми числами от
1 до
N.
S — это номер начальной
вершины.
M — это количество рёбер. Каждая из следующих
M строк содержит
три числа — номера начальной и конечной вершин текущего ребра и его вес
соответственно. Все веса положительны. Между двумя вершинами может быть
максимум одно ребро в каждом направлении.
Формат выходного файла
Выходной файл должен содержать
N чисел. Каждое
I-е число — это расстояние
от вершины до
S до вершины
I. Если некоторые вершины недостижимы из
S, то для
для них должно быть выведено
−1.
Ограничения
1 ≤ N, M ≤ 100000
Все веса меньше или равны
1000.
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
5 3 1
1 2 5
1 3 7
3 4 10
|
0 5 7 17 -1
|
