Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Re:貌似是求最小生成树中从源点到终点这条唯一路径中边长最大的，那么怎么求从源点到终点这条唯一路径中边长最大的？

Posted by united at 2009-11-23 11:19:29 on Problem 2253 and last updated at 2009-11-23 11:19:50
In Reply To:貌似是求最小生成树中从源点到终点这条唯一路径中边长最大的，那么怎么求从源点到终点这条唯一路径中边长最大的？ Posted by:15000 at 2009-10-18 11:43:50

其实就是求最小生成树，不过有一点点不一样。
起点总在点1，终点总在点2。用prim算法，从点1出发求最小生成树，将其它点依次纳入这个最
小生成树中。一旦点2被纳入就可以停止，因为这个时候我们已经确保可以从点1到达点2。输出
已生成的树所有边中最大值即可。

Followed by:

Post your reply here: