求条！！！！！！！！！

ZSYhaouuan @ 2024-12-08 16:43:01

#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct node{
    ll next,to,dis;
}egg[1000000+100];
ll head[1000000+100]={0},vis[1000000+100],dis[1000000+100],mx=(1<<31)-1;
ll n,m,s,cnt=0;
void add(ll from,ll to,ll dis){
    cnt++;
    egg[cnt].next=head[from];
    egg[cnt].dis=dis;
    egg[cnt].to=to;
    head[from]=cnt;
}
void dj(ll s){
    priority_queue<pair<ll,ll> > q;
    memset(dis,0x3f,sizeof dis);
    dis[s]=0;
    q.push(make_pair(0,s));
    while(q.size()){
        ll x=q.top().second;
        if(vis[x]) continue;
        vis[x]=1;
        q.pop();
        for(ll i=head[x];i;i=egg[i].next){
            ll y=egg[i].to;
            if(dis[y]>dis[x]+egg[i].dis){
                dis[y]=dis[x]+egg[i].dis;
                q.push(make_pair(-dis[y],y));
            }
        }
    }

    for(ll i=1;i<=n;i++){
        if(dis[i]>mx) cout<<mx<<" ";
        else cout<<dis[i]<<" ";
    }
}
int main(){
    cin>>n>>m>>s;
    for(ll i=1;i<=m;i++){
        ll x,y,z;
        cin>>x>>y>>z;
        add(x,y,z);
    }
    dj(s);
    return 0;
}

by kairuigg @ 2024-12-08 16:59:44

你的pop应该在continue前面，要不然会一直continue就不会往下走了

by kairuigg @ 2024-12-08 17:00:21

改成这样

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=2e5+5;
struct node{
    ll next,to,dis;
}egg[maxn];
ll head[maxn]={0},vis[maxn],dis[maxn];
ll mx=(1<<31)-1;
ll n,m,s,cnt=0;
void add(ll from,ll to,ll dis){
    cnt++;
    egg[cnt].next=head[from];
    egg[cnt].dis=dis;
    egg[cnt].to=to;
    head[from]=cnt;
}
void dj(ll s){
    priority_queue<pair<ll,ll> > q;
    memset(dis,0x3f,sizeof dis);
    dis[s]=0;
    q.push(make_pair(0,s));
    while(q.size()){
        ll x=q.top().second;
        q.pop();
        if(vis[x]) continue;
        vis[x]=1;
        for(ll i=head[x];i;i=egg[i].next){
            ll y=egg[i].to;
            if(dis[y]>dis[x]+egg[i].dis){
                dis[y]=dis[x]+egg[i].dis;
                q.push(make_pair(-dis[y],y));
            }
        }
    }
    for(ll i=1;i<=n;i++){
        if(dis[i]>mx) cout<<mx<<" ";
        else cout<<dis[i]<<" ";
    }
}
int main(){
    cin>>n>>m>>s;
    for(ll i=1;i<=m;i++){
        ll x,y,z;
        cin>>x>>y>>z;
        add(x,y,z);
    }
    dj(s);
    return 0;
}

by kairuigg @ 2024-12-08 17:01:19

@ZSYhaouuan

by ZSYhaouuan @ 2024-12-08 21:04:50

@kairuigg 谢谢一关