AcWing 903. 昂贵的聘礼    原题链接    中等

作者： 作者的头像   黄亦玫 ,  2020-06-20 10:24:16 ,  所有人可见 ,  阅读 605

1


踩了一个坑终于明白了

wa wa wa 一上午时间没了~~~~~~~

我的想法和y总的不一样，但是y总的更好。
建立一个虚拟点 只和1号点相连接 每次用上一个点来更新当前点 最后枚举一遍找到最小值。但是wa了
我用的是dijkstra算法 后来一想 dijkstra第一次找到的当前最小值就是最终的最小值但是这道题会把最小值变的更小，
所以不能用这个算法 但是spfa可以完美的避开这个问题，然后就过掉了， 开心

图论.png

5 评论

用户头像
itdef   2020-06-20 13:24         踩      回复

独立思考的习惯很棒 ORZ

用户头像
黄亦玫   2020-06-20 14:01         踩      回复

谢谢

用户头像
pfco   2020-06-20 11:48         踩      回复

可以举一个例子吗，这不是正权边的图吗，为什么Dijkstra不可以

用户头像
黄亦玫   2020-06-20 12:49         踩      回复

给你画了一个图，在本地里面，死活上传不了，我吐了。。。。

用户头像
pfco   2020-06-20 13:04    回复了 黄亦玫 的评论         踩      回复

我觉的可以发到打卡里面，我看一下，谢谢大佬