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

          TopCoder SRM 144 - PowerOutage

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


          主站蜘蛛池模板: 扬州市| 双辽市| 疏附县| 盱眙县| 门头沟区| 河池市| 额济纳旗| 内江市| 甘孜县| 都安| 霍州市| 潢川县| 揭西县| 信宜市| 赤水市| 封开县| 吴忠市| 乐山市| 偃师市| 万安县| 衡水市| 景洪市| 禹州市| 临城县| 广汉市| 灌云县| 库车县| 宝应县| 岐山县| 浦东新区| 周至县| 抚远县| 雅江县| 论坛| 盱眙县| 卢氏县| 茶陵县| 庆阳市| 曲周县| 历史| 本溪|