昂貴的聘礼 POJ - 1062

終于有一到中文的題了，好激動。哈哈哈。。。

題目大意：

ez要去搞對象，酋長的女兒。那不就是寒冰嘛。。。。 

大概就是個Bellford-Ford算法。開始理解的很亂，然后根據測試實例畫了個圖。

思路：

比如要是想要B需要100元，用A換就只需要20元，并且Ａ需要３０元。這件事就可以想成是，從A到B（單向）距離為20。但是從B為起點是100元，從A為起點需要30元。就是這個圖了嘛。黑色的就是從一個點到另一個點的花費。每個點底下的藍色的數就是從這個點出生的花費（生個好地方不容易?。?/strong>

然后就很顯然，以1號點為原點，bf一下，就得到了在不考慮出生花費的情況下，各個點到1號點的最小花費。然后這個花費加上出生花費最小的，就是到1號點的最小花費。

然后有一個很先進的等級系統，那幫人真是死要面子活受罪。這個酋長的地位是不是最高的啊，這個很重要！我猜是~ 15min后····靠！酋長的等級可能不是最高，坑爹啊。

然后解決辦法就是枚舉每一個等級區間，因為肯定要和酋長交易，所以就以酋長的等級為固定點。

最后就要娶到公主了~（這種背景的題，不猥瑣怎么行）

反思：

之后上網上查了別人的代碼。好像有一個思想叫超級源點什么的。意思就是，把在各個點出生的花費設成0號點到這些點的花費。這樣bf之后就可以直接出答案了。從抽象原理上應該是一樣的，我只是把從0號點引出的所有邊放到了外面。先把從各個頂點到1號頂點的最短路徑封裝起來，距離存為dis[i]。然后在看，從0到各個點再通過封裝好的路到1哪個花費最少。

不過這個超級源點思想（我也忘了是不是叫這個了，先這么記下來吧）倒是挺好。