使用STL和拓扑排序在图中查找最长路径

C++ Hard STL

任务 «使用STL和拓扑排序在图中查找最长路径»

给定一个有向无环图（DAG），包含 N 个顶点和 M 条边。每条边都有一个整数权重（可能为负）。需要找出从给定起始顶点 S 到所有其他顶点的最长路径长度。如果某个顶点不可达，则输出“INF”。请使用拓扑排序（Kahn 算法）和动态规划。限制条件：N ≤ 10^5，M ≤ 2*10^5，权重的绝对值 ≤ 10^9。保证图中不包含环。

输入格式

第一行：N M S（1 ≤ N ≤ 100000，0 ≤ M ≤ 200000，1 ≤ S ≤ N）。接下来的M行：u v w（1 ≤ u, v ≤ N，-10^9 ≤ w ≤ 10^9）。

输出格式

输出 N 行：对于每个顶点 i（从 1 到 N），输出从 S 到 i 的最长路径长度，如果顶点不可达，则输出“INF”。从 S 到 S 的路径长度视为 0。

示例

示例 1

输入

输出

示例 2

输入

2 1
2 -1
3 -2

输出

0
-1
-3

main.cpp