Countries in War (POJ 3114) Tarjan缩点+最短路

时间：2014-08-27 20:10:38 阅读：257 评论：0 收藏：0 [点我收藏+]

题目大意：

在一个有向图中，每两点间通信需要一定的时间，但同一个强连通分量里传递信息不用时间，给两点u，v求他们最小的通信时间。

解题过程：

1.首先把强连通分量缩点，然后遍历每一条边来更新两个强联通分量之间的距离。。

2.直接Floyd会超时，应该用dijstra或者spfa做k次最短路。

犯的错误：前向星数组开的太小，一直超时。

原文：http://www.cnblogs.com/vb4896/p/3940087.html

踩

(0)

评论一句话评论（0）

分享档案

更多>