Snowdream

I'm awake but my world is half asleep
posts - 403, comments - 310, trackbacks - 0, articles - 7
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

TopCoder SRM 144 - PowerOutage

Posted on 2007-08-14 17:12 ZelluX 阅读(386) 评论(0)  编辑  收藏 所属分类: Algorithm
一开始没看清题目,以为是在网状图中找遍历所有点的最短路径
后来才发现是在一棵树中,而且是从根节点出发,这个就简单多了
把所有路径加起来乘以2,就是从根节点到各个路径后再返回根节点所需的最短耗费。
然后再减掉访问最后一个节点后返回所需的耗费即可,既然要求最小的耗费就减去耗费最大的路径即可。

public class PowerOutage {
    
public static int estimateTimeOut(int[] fromJunction, int[] toJunction, int[] ductLength) {
        
int sum = 0;

        
for (int i = 0; i < ductLength.length; i++)
            sum 
+= ductLength[i];
        
        sum 
*= 2;
        sum 
-= findLongestWay(0, fromJunction, toJunction, ductLength);
        
return sum;
    }

    
public static int findLongestWay(int root, int[] fromJunction,
            
int[] toJunction, int[] ductLength) {
        
int max = 0;

        
for (int i = 0; i < fromJunction.length; i++) {
            
if (fromJunction[i] == root) {
                
int temp = findLongestWay(toJunction[i], fromJunction,
                             toJunction, ductLength) 
+ ductLength[i];
                
if (temp > max)
                    max 
= temp;
            }
        }

        
return max;
    }
}



只有注册用户登录后才能发表评论。


网站导航: