昂貴的聘礼 POJ - 1062

終于有一到中文的題了，好激動(dòng)。哈哈哈。。。

題目大意：

ez要去搞對(duì)象，酋長(zhǎng)的女兒。那不就是寒冰嘛。。。。 

大概就是個(gè)Bellford-Ford算法。開始理解的很亂，然后根據(jù)測(cè)試實(shí)例畫了個(gè)圖。

思路：

比如要是想要B需要100元，用A換就只需要20元，并且Ａ需要３０元。這件事就可以想成是，從A到B（單向）距離為20。但是從B為起點(diǎn)是100元，從A為起點(diǎn)需要30元。就是這個(gè)圖了嘛。黑色的就是從一個(gè)點(diǎn)到另一個(gè)點(diǎn)的花費(fèi)。每個(gè)點(diǎn)底下的藍(lán)色的數(shù)就是從這個(gè)點(diǎn)出生的花費(fèi)（生個(gè)好地方不容易啊）

然后就很顯然，以1號(hào)點(diǎn)為原點(diǎn)，bf一下，就得到了在不考慮出生花費(fèi)的情況下，各個(gè)點(diǎn)到1號(hào)點(diǎn)的最小花費(fèi)。然后這個(gè)花費(fèi)加上出生花費(fèi)最小的，就是到1號(hào)點(diǎn)的最小花費(fèi)。

然后有一個(gè)很先進(jìn)的等級(jí)系統(tǒng)，那幫人真是死要面子活受罪。這個(gè)酋長(zhǎng)的地位是不是最高的啊，這個(gè)很重要！我猜是~ 15min后····靠！酋長(zhǎng)的等級(jí)可能不是最高，坑爹啊。

然后解決辦法就是枚舉每一個(gè)等級(jí)區(qū)間，因?yàn)榭隙ㄒ颓蹰L(zhǎng)交易，所以就以酋長(zhǎng)的等級(jí)為固定點(diǎn)。

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

反思：

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

不過這個(gè)超級(jí)源點(diǎn)思想（我也忘了是不是叫這個(gè)了，先這么記下來吧）倒是挺好。