优先队列greater改less还能过?求助!

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

ikun_fjh @ 2023-07-13 21:04:40

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;

const int N = 1e5+5;

struct Edge{
    int y;
    int w;
};

struct Node {
  int y, d;
  bool operator < (const Node &n1) const {
    return d > n1.d;
  }
};

long long n , m , s , x , y , w;
vector<Edge> g[N];
long long d[N];
bool vis[N];
priority_queue<Node , vector<Node> , less<Node> > q;

void dijkstra(int sx)
{
    memset(d , 0x7f , sizeof(d));
    memset(vis , false , sizeof(vis));
    d[sx] = 0;
    q.push((Node) {sx,0});

    while(!q.empty())
    {
        Node n1 = q.top();
        int x = n1.y;
        q.pop();
        if(vis[x] == true)
        {
            continue;
        }
        vis[x] = true;
        for(int i = 0 ; i < g[x].size(); i++)
        {
            Edge nxt = g[x][i];
            int y = nxt.y;
            int w = nxt.w;
            if(vis[y]) continue;//
            if(d[x]+w < d[y])
            {
                d[y] = d[x] + w;
                //d[y] = min(d[y] , d[x]+w); 
                q.push((Node) {y, d[y]}); 
            }
        }
    }
}

int main()
{
    scanf("%d%d%d" , &n , &m , &s);
    //memset(a , 0x3f , sizeof(a));
    for(int i = 1 ; i <= m ; i++)
    {
        scanf("%d%d%d" , &x , &y , &w);
        g[x].push_back((Edge){y , w});
    }
    dijkstra(s);
    for(int i = 1 ; i <= n ; i++)
    {
        cout << d[i] << " ";
    }
    return 0;
}

求助大佬,为什么28行greater改less还能过?


by Claire0918 @ 2023-07-13 21:07:53

@fujiahe 堆优化只是优化,不一定要有。如果数据大一点就不行了。


by WsW_ @ 2023-07-13 21:14:02

@fujiahe 堆优化只是优化
你这相当于反向优化,使时间更劣,但能过


by ikun_fjh @ 2023-07-13 21:48:35

懂了,谢谢dalao


|