Posted on 2007-08-14 17:12
ZelluX 閱讀(481)
評論(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;
}
}