Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Re:不要被误导，此题不是最短路也不是最小生成树，而是FLOYD变体

Posted by Magic347 at 2010-12-21 15:14:55 on Problem 2253
In Reply To:不要被误导，此题不是最短路也不是最小生成树，而是FLOYD变体 Posted by:xuchang at 2010-08-17 08:58:35

> 不是最短路也不是最小生成树，所以用DIJ或者PRIM就算能AC也不一定对 


定义 f(i,j)为i->j的路径上的最大跳的最小值,

那么f(i,j)=min( f(i,j), max(f(i,k),f(k,j)) ),

o(n^3)

Followed by:

Post your reply here: