POJ - 1062 昂贵的聘礼 解题报告

昂贵的聘礼 POJ - 1062

终于有一到中文的题了，好激动。哈哈哈。。。

题目大意：

ez要去搞对象，酋长的女儿。那不就是寒冰嘛。。。。 

大概就是个Bellford-Ford算法。开始理解的很乱，然后根据测试实例画了个图。

思路：

比如要是想要B需要100元，用A换就只需要20元，并且Ａ需要３０元。这件事就可以想成是，从A到B（单向）距离为20。但是从B为起点是100元，从A为起点需要30元。就是这个图了嘛。黑色的就是从一个点到另一个点的花费。每个点底下的蓝色的数就是从这个点出生的花费（生个好地方不容易啊）

然后就很显然，以1号点为原点，bf一下，就得到了在不考虑出生花费的情况下，各个点到1号点的最小花费。然后这个花费加上出生花费最小的，就是到1号点的最小花费。

然后有一个很先进的等级系统，那帮人真是死要面子活受罪。这个酋长的地位是不是最高的啊，这个很重要！我猜是~ 15min后····靠！酋长的等级可能不是最高，坑爹啊。

然后解决办法就是枚举每一个等级区间，因为肯定要和酋长交易，所以就以酋长的等级为固定点。

最后就要娶到公主了~（这种背景的题，不猥琐怎么行）

反思：

之后上网上查了别人的代码。好像有一个思想叫超级源点什么的。意思就是，把在各个点出生的花费设成0号点到这些点的花费。这样bf之后就可以直接出答案了。从抽象原理上应该是一样的，我只是把从0号点引出的所有边放到了外面。先把从各个顶点到1号顶点的最短路径封装起来，距离存为dis[i]。然后在看，从0到各个点再通过封装好的路到1哪个花费最少。

不过这个超级源点思想（我也忘了是不是叫这个了，先这么记下来吧）倒是挺好。