EN
RU
ES
ZH
FR
DE
PT
AR
HI
Finding the longest path in a graph using STL and topological sorting
C++
Hard
STL
Task «Finding the longest path in a graph using STL and topological sorting»
Given a directed acyclic graph (DAG) with N vertices and M edges. Each edge has an integer weight (can be negative). It is necessary to find the length of the longest path from a given starting vertex S to all other vertices. If a vertex is unreachable, output "INF". Use topological sorting (Kahn's algorithm) and dynamic programming. Constraints: N ≤ 10^5, M ≤ 2*10^5, weights modulo ≤ 10^9. It is guaranteed that the graph contains no cycles.
Input Format
First line: N M S (1 ≤ N ≤ 100000, 0 ≤ M ≤ 200000, 1 ≤ S ≤ N). Next M lines: u v w (1 ≤ u, v ≤ N, -10^9 ≤ w ≤ 10^9).
Output Format
Output N lines: for each vertex i (from 1 to N), output the length of the longest path from S to i, or "INF" if the vertex is unreachable. The length of the path from S to S is considered to be 0.
Examples
Example 1
INPUT
4 3 1
1 2 5
1 3 3
2 4 2
OUTPUT
0
5
3
7
Example 2
INPUT
3 2 1
1 2 -1
2 3 -2
OUTPUT
0
-1
-3
main.cpp