蒟蒻求助！悬赏关注！

crzcqh @ 2023-08-15 14:54:39

#include<bits/stdc++.h>
#define M 100010
#include<queue> 
using namespace std;
struct node{
    int v,w,ne;
}e[M<<1]; 
int n,m,s,u,v,w,cnt;
int head[M],dis[M],vis[M];
void add(int u,int v,int w){
    e[++cnt].v=v;
    e[cnt].w=w;
    e[cnt].ne=head[u];
    head[u]=cnt;
}
priority_queue<int,vector<int>,greater<int> > q;
int main(){
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++) cin>>u>>v>>w,add(u,v,w);
    q.push(s);  
    for(int i=1;i<=n;i++) dis[i]=0x3f3f3f;
    dis[s]=0;
    while(!q.empty()){
        int t=q.top();
        vis[t]=1;
        q.pop();              
        for(int i=head[t];i;i=e[i].ne){
            int j=e[i].v;
            if(dis[j]>dis[t]+e[i].w){
                dis[j]=dis[t]+e[i].w;
                if(vis[j]) continue;
                q.push(j);
            }
        }
        //for(int i=1;i<=n;i++) cout<<vis[i]<<' ';
    }
    for(int i=1;i<=n;i++){
        cout<<dis[i]<<' ';
    }
    return 0;
}

by free_fall @ 2023-08-15 14:59:01

@crzcqh dis要开long long ，q中元素按照 dis 排序

by free_fall @ 2023-08-15 14:59:42

这样改:

#include<bits/stdc++.h>
#define M 100010
#include<queue> 
using namespace std;
struct node{
    int v,w,ne;
}e[M<<1]; 
int n,m,s,u,v,w,cnt;
int head[M],vis[M];
long long dis[M];
void add(int u,int v,int w){
    e[++cnt].v=v;
    e[cnt].w=w;
    e[cnt].ne=head[u];
    head[u]=cnt;
}
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
int main(){
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++) cin>>u>>v>>w,add(u,v,w);
    for(int i=1;i<=n;i++) dis[i]=0x3f3f3f3f3f3f3f;
    dis[s]=0;
    q.push({0,s});  
    while(!q.empty()){
        int t=q.top().second;
        q.pop();              
        if(vis[t]) continue;
        vis[t]=1;
        for(int i=head[t];i;i=e[i].ne){
            int j=e[i].v;
            if(dis[j]>dis[t]+e[i].w){
                dis[j]=dis[t]+e[i].w;
                q.push({dis[j],j});
            }
        }
        //for(int i=1;i<=n;i++) cout<<vis[i]<<' ';
    }
    for(int i=1;i<=n;i++){
        cout<<dis[i]<<' ';
    }
    return 0;
}

by crzcqh @ 2023-08-15 15:30:44

好的，谢谢！