做一道拆点的图论题时,需要用到堆优化的dijkstra,其中的堆存的是一个struct(参数大于2,pair放不下)
因为堆会自动排序,所以struct需要重载运算符。
注意:这两个模板是为了达到小根堆的效果
模板写法:
写法1:大根堆+重载小于号,但是返回的时候要反一下(返回与重载运算符相异)
struct Node //存储结点信息
{
int x, y, v; //x表示点编号,y表示最后一条小路的长度,v表示距离
bool operator< (const Node &t)const
{
//下面这句话的意思就是什么情况下当前元素排到下一个元素的后面,当前元素大于下一个元素就排到后面。
return v > t.v; //因为默认是大根堆,所以要把小于号变成大于号(与重载运算符相异)
}
};
priority_queue<Node> heap;
写法2:小根堆+重载大于号,返回的时候不需要反(返回与重载运算符相同)
struct Node //存储结点信息
{
int x, y, v; //x表示点编号,y表示最后一条小路的长度,v表示距离
bool operator> (const Node &t)const
{
return v > t.v; (小根堆,与重载运算符相同)
}
};
priority_queue<Node, vector<Node>, greater<Node>> heap;
上述两种写法都可以达到小根堆的效果,可以根据个人习惯决定使用哪一种。
PS:关于对重载大于号还是重载小于号的解释:
STL中绝大部分涉及排序的容器都使用到了小于号,最常见的如sort()
函数,所以要重载小于号。
小部分容器中使用到了greater
关键字,这类容器内部就会使用大于号(如小根堆),所以要重载大于号。
sort
降序排列的写法:
sort(q, q + n, greater<int>()); //q为数组名,n为数组长度