求助dij,悬赏4个关注

P4779 【模板】单源最短路径(标准版)

over_caykl @ 2023-06-27 19:21:09

#include<bits/stdc++.h>
#define PII pair<LL,int>
using namespace std;
const int N=2e5+5;
typedef long long LL;

int fst[N],nxt[N],t[N],v[N],tot;
void Add_edge(int a,int b,int c){
    nxt[++tot]=fst[a];
    fst[a]=tot;
    t[tot]=b;
    v[tot]=c;
}

int n,m,s;
LL Dis[N];
priority_queue<PII,vector<PII >,greater<PII> > Q;
bool inQ[N];
void Dij(){
    for(int i=1;i<=n;i++) Dis[i]=2147483647ll;
    Dis[s]=0ll;
    Q.push({Dis[s],s}); 
    inQ[s]=1;

    while(!Q.empty()){
        auto T=Q.top(); Q.pop();
        LL l=T.first; int r=T.second;

        for(int i=fst[r];i;i=nxt[i])
            if(Dis[t[i]]> l+v[i]){
                Dis[t[i]]= l+v[i];
                if(!inQ[t[i]]){
                    Q.push({Dis[t[i]],t[i]});
                    inQ[t[i]]=1;
                }
            }
    }
}
int A,B,C;
int main(){
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&A,&B,&C);
        Add_edge(A,B,C);
    }
    Dij();
    for(int i=1;i<=n;i++)
        printf("%lld ",Dis[i]);
    return 0;
}

只AC了第5个点


by liangbowen @ 2023-06-27 19:30:01

@over_caykl 改成这样即可过了呢,自己对比一下吧


by liangbowen @ 2023-06-27 19:30:24

@c20231020 \sum w_i\le10^9


by over_caykl @ 2023-06-27 19:32:09

@liangbowen 事实上,我一般写dij就是您给的这种写法。 故想问一下我这个帖子发得代码有什么错误awa。


by liangbowen @ 2023-06-27 19:33:58

@over_caykl 你这样写,每个点只会被更新到一次,显然错误的啊。


by over_caykl @ 2023-06-27 19:36:00

@liangbowen 魔怔了,谢谢


|