Timus #1450. Russian Pipelines

题目:有n个点,接下来输入m行,表示从a点到b点有向边距离为c,求从S(start)起点到F(Final)终点最大路径。

解析:求最大路径问题
1. Bellman-Ford算法
2. 拓扑,利用入度(In-degree)。从入度等于0(只可能有出度)的点开始拓扑,相邻的点入度-1代表还剩in-degree个点还没拓扑到他,如果该点所有可到他的点均已经寻找完,则把该点加入queue,即可以从该点进行下一步拓扑。

错误提示:
1. WA3 Dijskra算法写错
2. TLE16 Dijskra算法因为只要小于就要加入queue,比入度算法复杂度高,不要用Dijskra改版算法,换算法
3. WA9和WA10。小部分神奇原因:输出强制类型转换成int。大部分原因:不要第一个就从开始点开始拓扑(我也不知道为什么,就是错的)。

Bellman-Ford算法

In-degree

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

浙ICP备2021019730-1    浙公网安备 33010902002953号
Copyright © 2024 PanCake