posts - 403, comments - 310, trackbacks - 0, articles - 7
            BlogJava :: 首頁 :: 新隨筆 :: 聯系 :: 聚合  :: 管理

          TopCoder SRM 144 - PowerOutage

          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;
              }
          }


          主站蜘蛛池模板: 三台县| 闻喜县| 平昌县| 文登市| 高碑店市| 长沙县| 金沙县| 扎囊县| 涟源市| 康马县| 防城港市| 巨野县| 吉木萨尔县| 勃利县| 大化| 醴陵市| 天镇县| 滕州市| 吴忠市| 石门县| 库伦旗| 洛川县| 屏东县| 青岛市| 略阳县| 城步| 平谷区| 五指山市| 玛多县| 西盟| 读书| 古交市| 乌拉特后旗| 砀山县| 遂昌县| 将乐县| 正蓝旗| 崇信县| 奉节县| 周宁县| 新乐市|