顺便捞一个沉帖
https://www.luogu.org/discuss/show/92022
by lxy__ @ 2018-12-31 18:30:20
@[b612](/space/show?uid=138280) 能不能发一下完整代码？我怀疑他们堆的定义不太一样。
by yingjz @ 2018-12-31 18:30:55
@[b612](/space/show?uid=138280) 经过我实际测试，$16$ 分的代码应该是错误地定义了**大根堆**，而这两份代码在默认情况下定义的都是**大根堆**。
by yingjz @ 2018-12-31 18:33:53
@[YJZoier](/space/show?uid=31635)
博客链接
https://www.cnblogs.com/xzxl/p/7266404.html
题解链接
https://www.luogu.org/problemnew/solution/P4779
AC代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=200005;
int i,j,s,a,b,c,n,m,cnt=0;
int head[maxn],dis[maxn],vis[maxn];
struct Edge
{
int nxt,to,c;
};
Edge edge[maxn*3];
struct node
{
int id,dis;
bool operator<(const node &x)const
{
return x.dis < dis;
}
};
priority_queue<node>q;
void add(int x,int y,int c)
{
cnt++;
edge[cnt].nxt=head[x];
edge[cnt].to=y;
edge[cnt].c=c;
head[x]=cnt;
}
void dijkstra()
{
dis[s]=0;
q.push((node){s,0});
while(!q.empty())
{
int x=q.top().id,y=q.top().dis;
q.pop();
if(vis[x])
continue;
vis[x]=1;
for(int i=head[x];i;i=edge[i].nxt)
{
int w=edge[i].to;
if(dis[x]+edge[i].c<dis[w])
{
dis[w]=dis[x]+edge[i].c;
if(!vis[w])
q.push((node){w,dis[w]});
}
}
}
}
int main()
{
scanf("%d%d%d",&n,&m,&s);
memset(vis,0,sizeof(vis));
for(i=1;i<=n;i++)
dis[i]=0x7fffffff;
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
dijkstra();
for(i=1;i<=n;i++)
printf("%d ",dis[i]);
return 0;
}
16分代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=200005;
int i,j,s,a,b,c,n,m,cnt=0;
int head[maxn],dis[maxn],vis[maxn];
struct Edge
{
int nxt,to,c;
};
Edge edge[maxn*3];
struct node
{
int id,dis;
friend bool operator<(node x,node y)
{
return x.dis<y.dis;
}
};
priority_queue<node>q;
void add(int x,int y,int c)
{
cnt++;
edge[cnt].nxt=head[x];
edge[cnt].to=y;
edge[cnt].c=c;
head[x]=cnt;
}
void dijkstra()
{
dis[s]=0;
q.push((node){s,0});
while(!q.empty())
{
int x=q.top().id,y=q.top().dis;
q.pop();
if(vis[x])
continue;
vis[x]=1;
for(int i=head[x];i;i=edge[i].nxt)
{
int w=edge[i].to;
if(dis[x]+edge[i].c<dis[w])
{
dis[w]=dis[x]+edge[i].c;
if(!vis[w])
q.push((node){w,dis[w]});
}
}
}
}
int main()
{
scanf("%d%d%d",&n,&m,&s);
memset(vis,0,sizeof(vis));
for(i=1;i<=n;i++)
dis[i]=0x7fffffff;
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
dijkstra();
for(i=1;i<=n;i++)
printf("%d ",dis[i]);
return 0;
}
by lxy__ @ 2018-12-31 18:34:42
也就是说一个堆的定义是这样的：
```cpp
priority_queue<node> q;
```
而另外一个可能是这样的：
```cpp
priority_queue<node, vector<node>, greater<node> > q;
```
by yingjz @ 2018-12-31 18:35:17
@[YJZoier](/space/show?uid=31635) 感谢，不知用第一种写法有没有解决办法呢？
by lxy__ @ 2018-12-31 18:36:28
@[YJZoier](/space/show?uid=31635) 明白了，十分感谢
by lxy__ @ 2018-12-31 18:36:52
@[b612](/space/show?uid=138280) 重载的时候符号反过来
by yingjz @ 2018-12-31 18:37:31
@[YJZoier](/space/show?uid=31635) 已解决~
by lxy__ @ 2018-12-31 18:38:45
@[b612](/space/show?uid=138280) 其实仔细观察一下
```cpp
struct node
{
int id,dis;
friend bool operator<(node x,node y)
{
return x.dis<y.dis;
}
};
```
"能过样例，但是只有16分。"是因为他把小于号重载为小于号，所以**使用的是默认的大根堆。**
"题解dalao是这样写的"
其实他本质上已经把符号反过来了，你会发现 `x.dis < this->dis` 其实是把小于号重载为了大于号，**就不是默认的大根堆，而是相反的小根堆了**。
```cpp
struct node
{
int id,dis;
bool operator<(const node &x)const
{
return x.dis < dis;
}
};
```
by yingjz @ 2018-12-31 18:41:10