首页 > 其他 > 详细

说说关于洛谷P4779迪杰斯特拉的堆优化

时间:2019-05-12 21:44:54      阅读:138      评论:0      收藏:0      [点我收藏+]

众所周知,这题必须要用堆优化的迪杰斯特拉的堆优化才能过,否则60分(错失一等奖)

我没有得过一等奖但还是要说:

P4779

全过程:

struct node//堆中的比较函数 
{
    int dis;
    int pos;
    bool operator < (const node &x)const//在struct内部定义必须加const没有为何 
    {
        return x.dis<dis;//返回自己和自己比较的较小值
        //自己和自己类型的较小值!
        //如果在外面的话就要像平常一样定义两个const node &x,然后重载 
    }
};
priority_queue<node> q;//定义一个以node类型的优先队列(堆)
/*也就是说,我们定义了一个小根堆,
它包括两个元素,一个为dis(边的大小),另一个为pos,为当前节点,也就是dis[i]中的i
外加一个小根堆排序的条件,按dis大

技术分享图片

 

 

技术分享图片

——————by 长者の手迹

这个很形象了吧

 

说说关于洛谷P4779迪杰斯特拉的堆优化

原文:https://www.cnblogs.com/lbssxz/p/10853778.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!