這道千分題，其實是挺有意思的一題：
提供了點（這里是junction）和點之間的距離（或代價）；
要求以最短的距離（或最小代價）遍歷所有的點，同時每個點可以多次訪問；
初看之下，給人的感覺是圖論相關的問題，比如旅行者問題、歐拉環游之類。
在思考這個問題的時候，忽然間聯想到了圖論中的最小生成樹，雖然并不是真正要去得出最小生成樹，
但是按照最小生成樹所提供的思路--這點很重要--那就是圖和樹之間有著相當密切的關系：即使最小生
成樹并不能直接解決這個問題，但是它們之間存在的這層關系的確提供了解決問題的一個有益的嘗試方
向；
于是，思考進了一步，問題從“圖”簡化成了“樹”--如何把當前這個問題采用樹的結構和方法表達出
來：樹的根節點，很自然地想到了由問題中旅行的起始節點來表達；然后，隨著節點的不斷加入，樹就
自然地生成，此處的關鍵在于如何生成，或者說節點加入的規則，以及每個節點為了適應這個規則，所
必須持有的相關屬性信息：最直接的，父子節點之間的關系需要維護，從父節點到子節點的距離（或代
價）必須要保留，其次，考慮到如果每個節點都維護相關的距離（代價）信息，那么從當前節點到根節
點的代價也就可以由此遞推得出，進一步，我們所要求出的最短路徑（或最小代價）不就可以從上述這
些節點中維護的距離信息中得出嗎？這是非常關鍵的一步，它把當前我們構建的數據結構和問題的要求
之間建立起了相當直接的聯系。這說明我們目前思考的方向是有價值的而且極有可能順著這個方向前行
，可以得出相當不錯的結果。
顯然，既然要求最短路徑（最小代價），那么我們目前構建出的這顆Junction樹（因為其上的節點在題
中的物理含義是代表Junction，那這里我們就姑且稱其為Junction Tree），樹上的每個節點也應當保留
在其之下的子樹的最短路徑（最小代價），這就相當于把每個節點都作為根節點，然后求出各條子路徑
的代價，并比較得出最短路徑（最小代價），以及在這條最短路徑上的直接子節點；
每加入一個子節點，就要對上述已構建出的這些數據結構中的信息進行維護，以調整每個節點當前的最
短路徑代價和相應這條路徑上的直接子節點；當所有原“圖”中的“邊”信息，也就是
(fromJunction,toJuction,ductLength)所代表的（起始點，終止點，長度代價），都按照上述方案加入
Juction Tree之后，我們可以知道從最初的起始節點（也就是Junction Tree的根節點）到最終節點的（
Junction Tree上的某條路徑上的葉子節點）的最短（最小代價）路徑了。
對于Juction Tree這個ADT抽象數據結構的具體實現，考慮到優先隊列中二叉堆的經典實現往往使用數組
，同時也為了符合TC SRM一貫的簡捷明快的程序設計風格，我們這里同時使用幾個數組來維護前述構建
出的數據結構。
//////////////////////////////////////////////////////////////////////////////////////////
#include<cstdlib>
#include<vector>
#include<set>
using namespace std;
const int NIL = -1;
const int MAX = 50;
int Cost[MAX];
int ParentNode[MAX];
int MaxSubNode[MAX];
int MaxSubCost[MAX];
class PowerOutage
{
public:
int estimateTimeOut(vector<int> fromJunction, vector<int> toJunction, vector<int>
ductLength)
{
if (!CheckParameter(fromJunction, toJunction, ductLength)) return NIL;
Ini();
int count = fromJunction.size();
for (int i = 0; i < count; i++)
{
AddNode(fromJunction[i], toJunction[i], ductLength[i]);
}
return CalculateMinCost(fromJunction, toJunction, ductLength);
}
private:
void Ini()
{
memset(Cost, NIL, sizeof(int) * MAX);
memset(ParentNode, NIL, sizeof(int) * MAX);
memset(MaxSubNode, NIL, sizeof(int) * MAX);
memset(MaxSubCost, 0, sizeof(int) * MAX);
}
bool CheckParameter(const vector<int>& fromJunction, const vector<int>& toJunction,
const vector<int>& ductLength)
{
if (fromJunction.size() != toJunction.size() || toJunction.size() !=
ductLength.size())
return false;
return true;
}
void AddNode(int parent, int child, int cost)
{
if (parent < 0 || child < 0 || cost < 0) return;
Cost[child] = cost;
ParentNode[child] = parent;
int curParent = parent, curChild = child;
bool adjustParentCost = true;
while (adjustParentCost && curParent != NIL)
{
int candidateParentMaxSubCost = Cost[curChild] + MaxSubCost
[curChild];
if (MaxSubCost[curParent] < candidateParentMaxSubCost)
{
MaxSubCost[curParent] = candidateParentMaxSubCost;
MaxSubNode[curParent] = curChild;
curChild = curParent;
curParent = ParentNode[curParent];
}
else
{
adjustParentCost = false;
}
}
}
int CalculateMinCost(const vector<int>& fromJunction, const vector<int>&
toJunction, const vector<int>& ductLength)
{
int len = fromJunction.size();
int minCost = 0;
set<int> minCostPath;
minCostPath.insert(0);
int curNode = MaxSubNode[0];
while(curNode != NIL)
{
printf("%d;",curNode); // print the min cost path
minCostPath.insert(curNode);
curNode = MaxSubNode[curNode];
}
for (int i = 0; i < len; i++)
{
if (minCostPath.find(toJunction[i]) == minCostPath.end())
minCost += 2 * ductLength[i];
else
minCost += ductLength[i];
}
return minCost;
}
};