求神佬解答有关重载运算符和make_pair的一些问题

为什么重载运算符改成make_pair就好了？没改的话

戳这

这是改进前的代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,s;
struct Edge
{
    ll to,v,next;
}e[500010];
ll tot,dis[500010],head[500010],vis[500010];
struct cmp
{
    bool operator()(ll a,ll b){
        return dis[a]>dis[b];
    }
};
priority_queue<ll,vector<ll>,cmp> pq;

void Link(ll x,ll y,ll w){
    e[++tot].to=y;
    e[tot].v=w;
    e[tot].next=head[x];
    head[x]=tot;
}

void Dijsktra(){
    ll u,v;
    pq.push(s);
    while(!pq.empty()){
        u=pq.top(),pq.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(ll i=head[u];i;i=e[i].next){
            v=e[i].to;
            if(dis[v]>dis[u]+e[i].v){
                dis[v]=dis[u]+e[i].v;
                pq.push(v);
            }
        }
    }
}

int main()
{
    /*freopen("testdata.in","r",stdin);
    freopen("testdata.out","w",stdout);*/
    scanf("%lld%lld%lld",&n,&m,&s);
    for(ll i=1;i<=m;i++){
        ll x,y,w;
        scanf("%lld%lld%lld",&x,&y,&w);
        Link(x,y,w);
    }   
    for(ll i=1;i<=n;i++)
        dis[i]=2147483647;
    dis[s]=0;
    Dijsktra();
    for(ll i=1;i<n;i++)
        printf("%lld ",dis[i]);
    printf("%lld\n",dis[n]);
    return 0;
}

这是改进后的代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,s;
struct Edge
{
    ll to,v,next;
}e[500010];
ll tot,dis[500010],head[500010],vis[500010];
priority_queue< pair<int,int> > pq;

void Link(ll x,ll y,ll w){
    e[++tot].to=y;
    e[tot].v=w;
    e[tot].next=head[x];
    head[x]=tot;
}

void Dijsktra(){
    ll u,v;
    pq.push(make_pair(0,s));
    while(!pq.empty()){
        u=pq.top().second;pq.pop();
        if(vis[u]) {
            continue;
        }
        vis[u]=1;
        for(ll i=head[u];i;i=e[i].next){
            v=e[i].to;
            if(dis[v]>dis[u]+e[i].v){
                dis[v]=dis[u]+e[i].v;
                pq.push(make_pair(-dis[v],v));
            }
        }
    }
}

int main()
{
    /*freopen("testdata.in","r",stdin);
    freopen("testdata.out","w",stdout);*/
    scanf("%lld%lld%lld",&n,&m,&s);
    for(ll i=1;i<=m;i++){
        ll x,y,w;
        scanf("%lld%lld%lld",&x,&y,&w);
        Link(x,y,w);
    }   
    for(ll i=1;i<=n;i++)
        dis[i]=1e10;
    dis[s]=0;
    Dijsktra();
    for(ll i=1;i<n;i++)
        printf("%lld ",dis[i]);
    printf("%lld\n",dis[n]);
    return 0;
}

这是题解

#include<bits/stdc++.h>
#define M(x,y) make_pair(x,y)
using namespace std;
int fr[100010],to[200010],nex[200010],v[200010],tl,d[100010];
bool b[100010];
void add(int x,int y,int w){
    to[++tl]=y;
    v[tl]=w;
    nex[tl]=fr[x];
    fr[x]=tl;
}
priority_queue< pair<int,int> > q;
int main(){
    int n,m,x,y,z,s;
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
    }
    for(int i=1;i<=n;i++) d[i]=1e10;
    d[s]=0;
    q.push(M(0,s));
    while(!q.empty()){
        int x=q.top().second;
        q.pop(); 
        if(b[x]) continue;
        b[x]=1;
        for(int i=fr[x];i;i=nex[i]){
            int y=to[i],l=v[i];
            if(d[y]>d[x]+l){
                d[y]=d[x]+l;
                q.push(M(-d[y],y));//懒得重载运算符
            }
        }
    }
    for(int i=1;i<=n;i++) printf("%d ",d[i]);
    return 0;
}