Home | Problems | Discuss | Login

  

此题如何寻找变为l/2的边?

3335: Windy's Route

剑魔 | 2009-05-26 21:48:38 | delete | edit
首先如果有同一点指向同一点的那些边,直接忽略.
1.用spfa求没有折半路径的单源最短路
2.用spfa更新每个点含有一条折半路径的情况下的最短路.
如果题目明确是无环的
1.dijkstra或spfa
2.按拓扑顺序更新折半路径或者spfa 
vegebird | 2009-05-26 20:54:42 | delete | edit
同样纠结中 
ycwyyq | 2009-05-26 20:41:26 | delete | edit
RT
 

Please login to reply.