PT
RU
EN
ES
ZH
FR
DE
AR
HI
Busca do caminho mais longo em um grafo usando STL e ordenação topológica
C++
Hard
STL
Tarefa «Busca do caminho mais longo em um grafo usando STL e ordenação topológica»
Dado um grafo direcionado acíclico (DAG) com N vértices e M arestas. Cada aresta possui um peso inteiro (podendo ser negativo). É necessário encontrar o comprimento do caminho mais longo do vértice inicial S para todos os outros vértices. Se o vértice for inalcançável, imprima «INF». Use ordenação topológica (algoritmo de Kahn) e programação dinâmica. Restrições: N ≤ 10^5, M ≤ 2*10^5, pesos em módulo ≤ 10^9. Garante-se que o grafo não contém ciclos.
Formato de Entrada
Primeira linha: N M S (1 ≤ N ≤ 100000, 0 ≤ M ≤ 200000, 1 ≤ S ≤ N). Próximas M linhas: u v w (1 ≤ u, v ≤ N, -10^9 ≤ w ≤ 10^9).
Formato de Saída
Imprima N linhas: para cada vértice i (de 1 a N) imprima o comprimento do caminho mais longo de S até i, ou «INF» se o vértice for inalcançável. O comprimento do caminho de S até S é considerado 0.
Exemplos
Exemplo 1
ENTRADA
4 3 1
1 2 5
1 3 3
2 4 2
SAÍDA
0
5
3
7
Exemplo 2
ENTRADA
3 2 1
1 2 -1
2 3 -2
SAÍDA
0
-1
-3
main.cpp