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

          TopCoder SRM 144 - PowerOutage

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


          主站蜘蛛池模板: 财经| 营山县| 郸城县| 武威市| 凤冈县| 西城区| 肇州县| 华宁县| 察雅县| 高青县| 福建省| 肇东市| 陕西省| 崇义县| 北川| 阜阳市| 枣强县| 枣阳市| 神木县| 邓州市| 湄潭县| 峨山| 泰宁县| 贺州市| 城口县| 左权县| 沈阳市| 安阳县| 南乐县| 漳州市| 屏南县| 岱山县| 北安市| 盖州市| 屯门区| 普安县| 大余县| 突泉县| 叶城县| 庐江县| 周至县|