RU
EN
ES
ZH
FR
DE
PT
AR
HI
Поиск самого длинного пути в графе с использованием STL и топологической сортировки
C++
Сложный
STL
Задача «Поиск самого длинного пути в графе с использованием STL и топологической сортировки»
Дан ориентированный ациклический граф (DAG) с N вершинами и M ребрами. Каждое ребро имеет целочисленный вес (может быть отрицательным). Необходимо найти длину самого длинного пути от заданной начальной вершины S до всех остальных вершин. Если вершина недостижима, вывести «INF». Используйте топологическую сортировку (алгоритм Кана) и динамическое программирование. Ограничения: N ≤ 10^5, M ≤ 2*10^5, веса по модулю ≤ 10^9. Гарантируется, что граф не содержит циклов.
Формат ввода
Первая строка: N M S (1 ≤ N ≤ 100000, 0 ≤ M ≤ 200000, 1 ≤ S ≤ N). Следующие M строк: u v w (1 ≤ u, v ≤ N, -10^9 ≤ w ≤ 10^9).
Формат вывода
Выведите N строк: для каждой вершины i (от 1 до N) выведите длину самого длинного пути от S до i, или «INF», если вершина недостижима. Длина пути от S до S считается равной 0.
Примеры
Пример 1
ВВОД
4 3 1
1 2 5
1 3 3
2 4 2
ВЫВОД
0
5
3
7
Пример 2
ВВОД
3 2 1
1 2 -1
2 3 -2
ВЫВОД
0
-1
-3
main.cpp