FR
RU
EN
ES
ZH
DE
PT
AR
HI
Recherche du plus long chemin dans un graphe à l'aide de STL et du tri topologique
C++
Hard
STL
Tâche «Recherche du plus long chemin dans un graphe à l'aide de STL et du tri topologique»
Un graphe orienté acyclique (DAG) avec N sommets et M arêtes est donné. Chaque arête a un poids entier (pouvant être négatif). Il faut trouver la longueur du plus long chemin depuis un sommet de départ donné S vers tous les autres sommets. Si un sommet est inaccessible, afficher « INF ». Utilisez le tri topologique (algorithme de Kahn) et la programmation dynamique. Contraintes : N ≤ 10^5, M ≤ 2*10^5, poids en valeur absolue ≤ 10^9. Il est garanti que le graphe ne contient pas de cycles.
Format d\ entrée
Première ligne : N M S (1 ≤ N ≤ 100000, 0 ≤ M ≤ 200000, 1 ≤ S ≤ N). Les M lignes suivantes : u v w (1 ≤ u, v ≤ N, -10^9 ≤ w ≤ 10^9).
Format de sortie
Affichez N lignes : pour chaque sommet i (de 1 à N), affichez la longueur du plus long chemin de S à i, ou « INF » si le sommet est inaccessible. La longueur du chemin de S à S est considérée comme égale à 0.
Exemples
Exemple 1
ENTRÉE
4 3 1
1 2 5
1 3 3
2 4 2
SORTIE
0
5
3
7
Exemple 2
ENTRÉE
3 2 1
1 2 -1
2 3 -2
SORTIE
0
-1
-3
main.cpp