這道千分題，其實(shí)是挺有意思的一題：
提供了點(diǎn)（這里是junction）和點(diǎn)之間的距離（或代價）；
要求以最短的距離（或最小代價）遍歷所有的點(diǎn)，同時每個點(diǎn)可以多次訪問；
初看之下，給人的感覺是圖論相關(guān)的問題，比如旅行者問題、歐拉環(huán)游之類。
在思考這個問題的時候，忽然間聯(lián)想到了圖論中的最小生成樹，雖然并不是真正要去得出最小生成樹，
但是按照最小生成樹所提供的思路--這點(diǎn)很重要--那就是圖和樹之間有著相當(dāng)密切的關(guān)系：即使最小生
成樹并不能直接解決這個問題，但是它們之間存在的這層關(guān)系的確提供了解決問題的一個有益的嘗試方
向；
于是，思考進(jìn)了一步，問題從“圖”簡化成了“樹”--如何把當(dāng)前這個問題采用樹的結(jié)構(gòu)和方法表達(dá)出
來：樹的根節(jié)點(diǎn)，很自然地想到了由問題中旅行的起始節(jié)點(diǎn)來表達(dá)；然后，隨著節(jié)點(diǎn)的不斷加入，樹就
自然地生成，此處的關(guān)鍵在于如何生成，或者說節(jié)點(diǎn)加入的規(guī)則，以及每個節(jié)點(diǎn)為了適應(yīng)這個規(guī)則，所
必須持有的相關(guān)屬性信息：最直接的，父子節(jié)點(diǎn)之間的關(guān)系需要維護(hù)，從父節(jié)點(diǎn)到子節(jié)點(diǎn)的距離（或代
價）必須要保留，其次，考慮到如果每個節(jié)點(diǎn)都維護(hù)相關(guān)的距離（代價）信息，那么從當(dāng)前節(jié)點(diǎn)到根節(jié)
點(diǎn)的代價也就可以由此遞推得出，進(jìn)一步，我們所要求出的最短路徑（或最小代價）不就可以從上述這
些節(jié)點(diǎn)中維護(hù)的距離信息中得出嗎？這是非常關(guān)鍵的一步，它把當(dāng)前我們構(gòu)建的數(shù)據(jù)結(jié)構(gòu)和問題的要求
之間建立起了相當(dāng)直接的聯(lián)系。這說明我們目前思考的方向是有價值的而且極有可能順著這個方向前行
，可以得出相當(dāng)不錯的結(jié)果。
顯然，既然要求最短路徑（最小代價），那么我們目前構(gòu)建出的這顆Junction樹（因?yàn)槠渖系墓?jié)點(diǎn)在題
中的物理含義是代表Junction，那這里我們就姑且稱其為Junction Tree），樹上的每個節(jié)點(diǎn)也應(yīng)當(dāng)保留
在其之下的子樹的最短路徑（最小代價），這就相當(dāng)于把每個節(jié)點(diǎn)都作為根節(jié)點(diǎn)，然后求出各條子路徑
的代價，并比較得出最短路徑（最小代價），以及在這條最短路徑上的直接子節(jié)點(diǎn)；
每加入一個子節(jié)點(diǎn)，就要對上述已構(gòu)建出的這些數(shù)據(jù)結(jié)構(gòu)中的信息進(jìn)行維護(hù)，以調(diào)整每個節(jié)點(diǎn)當(dāng)前的最
短路徑代價和相應(yīng)這條路徑上的直接子節(jié)點(diǎn)；當(dāng)所有原“圖”中的“邊”信息，也就是
(fromJunction,toJuction,ductLength)所代表的（起始點(diǎn)，終止點(diǎn)，長度代價），都按照上述方案加入
Juction Tree之后，我們可以知道從最初的起始節(jié)點(diǎn)（也就是Junction Tree的根節(jié)點(diǎn)）到最終節(jié)點(diǎn)的（
Junction Tree上的某條路徑上的葉子節(jié)點(diǎn)）的最短（最小代價）路徑了。
對于Juction Tree這個ADT抽象數(shù)據(jù)結(jié)構(gòu)的具體實(shí)現(xiàn)，考慮到優(yōu)先隊(duì)列中二叉堆的經(jīng)典實(shí)現(xiàn)往往使用數(shù)組
，同時也為了符合TC SRM一貫的簡捷明快的程序設(shè)計(jì)風(fēng)格，我們這里同時使用幾個數(shù)組來維護(hù)前述構(gòu)建
出的數(shù)據(jù)結(jié)構(gòu)。
//////////////////////////////////////////////////////////////////////////////////////////
#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;
}
};