Suche nach dem längsten Pfad in einem Graphen mit STL und topologischer Sortierung

C++ Hard STL

Aufgabe «Suche nach dem längsten Pfad in einem Graphen mit STL und topologischer Sortierung»

Gegeben ist ein gerichteter azyklischer Graph (DAG) mit N Knoten und M Kanten. Jede Kante hat ein ganzzahliges Gewicht (kann negativ sein). Es ist erforderlich, die Länge des längsten Pfades von einem gegebenen Startknoten S zu allen anderen Knoten zu finden. Wenn ein Knoten nicht erreichbar ist, geben Sie „INF“ aus. Verwenden Sie die topologische Sortierung (Kahn-Algorithmus) und dynamische Programmierung. Einschränkungen: N ≤ 10^5, M ≤ 2*10^5, Gewichte modulo ≤ 10^9. Es wird garantiert, dass der Graph keine Zyklen enthält.

Eingabeformat

Erste Zeile: N M S (1 ≤ N ≤ 100000, 0 ≤ M ≤ 200000, 1 ≤ S ≤ N). Die folgenden M Zeilen: u v w (1 ≤ u, v ≤ N, -10^9 ≤ w ≤ 10^9).

Ausgabeformat

Geben Sie N Zeilen aus: Für jeden Knoten i (von 1 bis N) geben Sie die Länge des längsten Pfades von S zu i aus, oder „INF“, wenn der Knoten nicht erreichbar ist. Die Pfadlänge von S zu S wird als 0 angenommen.

Beispiele

Beispiel 1

EINGABE

AUSGABE

Beispiel 2

EINGABE

2 1
2 -1
3 -2

AUSGABE

0
-1
-3

main.cpp