dij全RE求调（悬赏一关注）

114514xxx @ 2024-07-13 21:23:58

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=500025;
inline int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'|c>'9'){
        if(c=='-')f*=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
} 
int n,m,s;
struct edge{
    int to,wei,nextt;
}g[N];
int cnt,head[N],vis[N],ans[N];
struct pri{
    int id,ans;
    bool operator <(const pri&x) const{
        x.ans<ans;
    }
};
priority_queue<pri>q;
void add(int x,int y,int z){
    ++cnt;
    g[cnt].nextt=head[x];
    g[cnt].wei=z;
    g[cnt].to=y;
    head[x]=cnt;
}
void dijkstra(){
    while(!q.empty()){
        pri t=q.top();
        q.pop();
        int u=t.id;
        if(!vis[u]){
            vis[u]=1;
            for(int i=head[u];i;i=g[i].nextt){
                int v=g[i].to;
                if(ans[v]>ans[u]+g[i].wei){
                    ans[v]=ans[u]+g[i].wei;
                    if(!vis[v])
                        q.push(pri{v,ans[v]});
                }
            }
        }
    }
}
signed main(){
    memset(ans,0x3f,sizeof(ans));
    n=read();m=read();s=read();
    int x,y,z;
    for(int i=1;i<=m;i++){
        x=read();y=read();z=read();
        add(x,y,z);
    }
    ans[s]=0;
    q.push(pri{s,0});
    dijkstra();
    for(int i=1;i<=n;i++)
        cout<<ans[i]<<' ';
    return 0;
}

by Discorder_ @ 2024-07-13 21:53:28

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=500025;
inline int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f*=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
} 
int n,m,s;
struct edge{
    int to,wei,nextt;
}g[N];
int cnt,head[N],vis[N],ans[N];
struct pri{
    int id,ans;
    bool operator <(const pri&x) const{
        return x.ans<ans;
    }
};
priority_queue<pri>q;
void add(int x,int y,int z){
    ++cnt;
    g[cnt].nextt=head[x];
    g[cnt].wei=z;
    g[cnt].to=y;
    head[x]=cnt;
}
void dijkstra(){
    while(!q.empty()){
        pri t=q.top();
        q.pop();
        int u=t.id;
        if(!vis[u]){
            vis[u]=1;
            for(int i=head[u];i;i=g[i].nextt){
                int v=g[i].to;
                if(ans[v]>ans[u]+g[i].wei){
                    ans[v]=ans[u]+g[i].wei;
                    if(!vis[v])
                        q.push(pri{v,ans[v]});
                }
            }
        }
    }
}
signed main(){
    memset(ans,0x3f,sizeof(ans));
    n=read();m=read();s=read();
    int x,y,z;
    for(int i=1;i<=m;i++){
        x=read();y=read();z=read();
        add(x,y,z);
    }
    ans[s]=0;
    q.push(pri{s,0});
    dijkstra();
    for(int i=1;i<=n;i++)
        cout<<ans[i]<<' ';
    return 0;
}

快读少了一个'|',结构体的重载少了return 自己改一下

by 114514xxx @ 2024-07-13 21:56:31

@Stasis_ %%%