Posted on 2007-08-14 17:12
ZelluX 阅读(475)
评论(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;
}
}