Búsqueda del camino más largo en un grafo usando STL y ordenamiento topológico

C++ Hard STL

Tarea «Búsqueda del camino más largo en un grafo usando STL y ordenamiento topológico»

Dado un grafo acíclico dirigido (DAG) con N vértices y M aristas. Cada arista tiene un peso entero (puede ser negativo). Es necesario encontrar la longitud del camino más largo desde un vértice inicial dado S hasta todos los demás vértices. Si un vértice es inalcanzable, mostrar «INF». Utilice ordenamiento topológico (algoritmo de Kahn) y programación dinámica. Restricciones: N ≤ 10^5, M ≤ 2*10^5, pesos en módulo ≤ 10^9. Se garantiza que el grafo no contiene ciclos.

Formato de entrada

Primera línea: N M S (1 ≤ N ≤ 100000, 0 ≤ M ≤ 200000, 1 ≤ S ≤ N). Las siguientes M líneas: u v w (1 ≤ u, v ≤ N, -10^9 ≤ w ≤ 10^9).

Formato de salida

Imprima N líneas: para cada vértice i (de 1 a N) imprima la longitud del camino más largo desde S hasta i, o «INF» si el vértice es inalcanzable. La longitud del camino desde S hasta S se considera igual a 0.

Ejemplos

Ejemplo 1

ENTRADA

SALIDA

Ejemplo 2

ENTRADA

2 1
2 -1
3 -2

SALIDA

0
-1
-3

main.cpp