样例五wa了

14425aab @ 2024-04-10 15:22:29

#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>

using namespace std;

const int INF = 0x3f3f3f3f;

const int N = 1e6;
typedef long long LL;

LL dist[N];
int h[N],e[N],ne[N],idx=1,w[N];

bool vis[N];

int n,m,s;

struct node
{
    LL v,l;
    friend bool operator<(node a,node b)
    {
        return a.l>b.l;
    }
}tmp;

int d=(1<<31)-1;

void add(int a,int b,int c)
{
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
}

void Dijkstra()
{
    dist[s]=0;
    tmp.v=s;
    tmp.l=0;
    priority_queue<node> q;
    q.push(tmp);
    while(!q.empty())
    {
        int u=q.top().v;
        q.pop();
        if(vis[u]) continue;
        vis[u]=true;
        for(int i=h[u];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>dist[u]+w[i]&&!vis[j])
            {
                dist[j]=dist[u]+w[i];
                struct node New;
                New.v=j;
                New.l=dist[j];
                q.push(New);
            }
        }
    }
}
int main()
{
    cin>>n>>m>>s;
    memset(h,-1,sizeof h);
    memset(dist,0x3f,sizeof dist);
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }
    Dijkstra();
    for(int i=1;i<=n;i++)
    {
        if(dist[i]>INF/2) cout<<d<<" ";
        else cout<<dist[i]<<" ";
    }
    return 0;
}

by 红黑树 @ 2024-04-10 15:31:09

@14425aab

#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>

using namespace std;

const int INF = 2e9;

const int N = 1e6;
typedef long long LL;

LL dist[N];
int h[N],e[N],ne[N],idx=1,w[N];

bool vis[N];

int n,m,s;

struct node
{
    LL v,l;
    friend bool operator<(node a,node b)
    {
        return a.l>b.l;
    }
}tmp;

int d=(1<<31)-1;

void add(int a,int b,int c)
{
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
}

void Dijkstra()
{
    dist[s]=0;
    tmp.v=s;
    tmp.l=0;
    priority_queue<node> q;
    q.push(tmp);
    while(!q.empty())
    {
        int u=q.top().v;
        q.pop();
        if(vis[u]) continue;
        vis[u]=true;
        for(int i=h[u];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>dist[u]+w[i]&&!vis[j])
            {
                dist[j]=dist[u]+w[i];
                struct node New;
                New.v=j;
                New.l=dist[j];
                q.push(New);
            }
        }
    }
}
int main()
{
    cin>>n>>m>>s;
    memset(h,-1,sizeof h);
    memset(dist,0x3f,sizeof dist);
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }
    Dijkstra();
    for(int i=1;i<=n;i++)
    {
        if(dist[i]>INF/2) cout<<d<<" ";
        else cout<<dist[i]<<" ";
    }
    return 0;
}

by 14425aab @ 2024-04-10 15:37:50

@红黑树 谢谢佬！！

by 14425aab @ 2024-04-10 15:41:26

@红黑树 想再问老哥一个问题：这个模板程序在结构体里重载 < 时，为什么要用a.l>b.l，不是要构建最小根堆吗,这样的话不就是从大到小排了吗？那不就是最大堆吗？

by 红黑树 @ 2024-04-10 17:23:02

@14425aab priority_queue 比较特殊，他默认是大根堆，但是你可以通过这样的反向操作使他变成小根堆。

by 14425aab @ 2024-04-10 18:23:41

@红黑树 ok,谢谢