wcwswswws的日记

wcwswswws

sgu352

     题意:王国有N个城市(1~N),首都在1。已知有M条路,其中N-1条路构成一棵树T,保证从首都到所有节点的最短路都在这棵树上。现在要求每个节点在当树T上从1到该节点的路径的最后一条边坏掉的情况下的从1到它的最短路。

      LCA。对于每个节点v,题目所求的最短路或者是在它的子树T'外的点连一条边到它,或者是在它的子树T'外的点连一条边到T‘中任意一点,延最初的最短路走到该点。这样,对于每个节点,处理每条与其相连的不在树T上的边。设边上另一点为u,则按照LCA(u,v)=i不同值建立不同的集合Ti。然后按照从1到v的路径的顺序来,每次在当前可使用的边选出最小值加上沿树T往上走到节点i的值去更新对于i的答案,同时把Ti中所有边置为可使用。

posted on 2012-02-21 23:45 世界厕所所长 阅读(177) 评论(0)  编辑 收藏 引用 所属分类: ACM/ICPC


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理