Ayaka_T @ 2022-04-07 14:14:34
Rt,dij这样重载是可以通过的:
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
struct node{
int to,v;
bool operator < (const node &x)const
{
return x.v<v;
}
};
vector<node>d[maxn];
priority_queue<node>q;
int n,m,s,u,v,to,ans[maxn];
bool vis[maxn];
void dij(){
memset(ans,0x3f,sizeof ans);
ans[s]=0;
q.push({s,0});
while(!q.empty()){
node now=q.top();
q.pop();
if(vis[now.to])continue;
vis[now.to]=true;
for(int i=0;i<d[now.to].size();i++){
node next=d[now.to][i];
if(ans[next.to]>ans[now.to]+next.v){
ans[next.to]=ans[now.to]+next.v;
q.push({next.to,ans[next.to]});
}
}
}
for(int i=1;i<=n;i++){
printf("%d ",ans[i]);
}
}
int main(){
scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&u,&v,&to);
d[u].push_back({v,to});
}
dij();
return 0;
}
而将重载的部分改为这样:
friend const bool operator <(node x,node y){
return x.v<y.v;
}
就无法通过
改成这样就可以通过:
friend bool operator<(node x,node y){
if(x.v<y.v)
return false;
else
return true;
}
或这样也可以
friend bool operator<(node x,node y)
{
return x.v>y.v;
}
问题:
1,为什么定义大根堆要重载小于号
2,为什么用友元重载时,函数内就要反着过来
望解答,谢谢!
by Mzk2333 @ 2022-04-07 14:17:06
第一个模板下会先判断<
,条件就反了,即当x.v<y.v
时才会返回真,与你第二个AC代码完全不一样。
by 蒟酱 @ 2022-04-07 14:21:13
@tanjianlang
你那个不写友元的也是反的……仔细想想为什么
c++ STL 里面都是重载小于号,然后 STL 的优先队列默认是大根堆而不是小根堆,所以只能反着重载运算符
by Terrible @ 2022-04-07 15:17:47
并非都需要友元函数的形式,常函数、体外定义都可以。
by Ayaka_T @ 2022-04-07 17:28:08
@蒟酱 所以第一个模板是可以理解为这样吗?
bool operator < (const node &x)const
{
return v>x.v;
}
另外,为什么我改为小根堆后重载小于号就会报错,要重载大于号才行,想问这是为什么
by 蒟酱 @ 2022-04-07 18:56:00
@tanjianlang
1.确实
2.STL 里面都是重载小于号的
by Ayaka_T @ 2022-04-08 13:59:44
@蒟酱 明白了,万分感谢