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

          TopCoder SRM 144 - PowerOutage

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


          主站蜘蛛池模板: 铁岭市| 遵化市| 土默特右旗| 湘潭市| 横山县| 玉环县| 攀枝花市| 丹东市| 长沙市| 轮台县| 江源县| 渝北区| 辰溪县| 靖西县| 泰和县| 延津县| 含山县| 夏津县| 乌拉特中旗| 承德县| 都兰县| 轮台县| 江安县| 上林县| 东海县| 磴口县| 成都市| 正蓝旗| 松潘县| 合肥市| 海口市| 阳城县| 湘潭县| 阜新| 五莲县| 边坝县| 朔州市| 武义县| 洪湖市| 田林县| 富民县|