第19到21行代码是什么意思,求助

P4779 【模板】单源最短路径(标准版)

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 哈哈这个我知道,但是我想知道这行代码的解释不是意思,但是还是谢谢大佬


|