CurryNo_1 @ 2023-03-09 22:14:29
//迪杰斯特拉算法+堆优化(优先队列)解决单源最短路径问题模板
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<memory>
#include<queue>
#define INF 0x7fffffff
using namespace std;
typedef long long ll;
const int N=2e5+10;
int n,m,s,x,y,w,cnt,first[N];
bool vis[N];
ll dis[N];
struct node{
int ans;
int id;
bool operator < (const node&x) const
{
return ans>x.ans;
}
};
struct edge{
int to;
int w;
int next;
}edges[N];
void add(int u,int v,int w)
{
edges[++cnt].w=w;
edges[cnt].to=v;
edges[cnt].next=first[u];
first[u]=cnt;
}
priority_queue<node>q;//优先队列按照到起点的距离从小到大排序
int main()
{
cin >> n >> m >> s;
for(int i=1;i<=n;i++) dis[i]=INF;
dis[s]=0;
for(int i=1;i<=m;i++)//链式前向星储存数据
{
cin >> x >> y >> w;
add(x,y,w);
}
q.push(node{0,s});
while(!q.empty())
{
node tmp=q.top();//优先队列的堆顶元素即当前距离起点最近的元素
q.pop();
int pos=tmp.id;
if(!vis[pos])
{
vis[pos]=1;
for(int i=first[pos];i!=0;i=edges[i].next)
{
int to=edges[i].to;
if(dis[to]>dis[pos]+edges[i].w)
{
dis[to]=dis[pos]+edges[i].w;
if(!vis[to]) q.push(node{dis[to],to});
}
}
}
}
for(int i=1;i<=n;i++) cout << dis[i] << " ";
return 0;
}
第19到21行代码重载的是什么意思
by Iniaugoty @ 2023-03-09 22:17:31
到一个点的最短路比到另一个点的更短,这个点在队列里就更优先,反之亦然。
by CurryNo_1 @ 2023-03-15 21:25:39
@gty314159 哈哈这个我知道,但是我想知道这行代码的解释不是意思,但是还是谢谢大佬