堆优化 T 飞了,求助

P1342 请柬

DicaprioD @ 2024-04-29 18:51:34

只过了第 4 个点,题解说的方法都加了,要爆炸了,大佬帮忙看看要改哪 orz orz

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N=1e6+10;
int n,m;
int ne[N],e[N],h[N],idx,w[N];
int ne1[N],e1[N],h1[N],idx1,w1[N];
int d[N],d1[N];
bool st[N],st1[N];
int ans;
inline void add(int a,int b,int c){
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
inline void add1(int a,int b,int c){
    e1[idx1] = b, ne1[idx1] = h1[a], w1[idx1] = c, h1[a] = idx1++;
}
inline void Dijkstra(int s){
    for(register int i=1;i<=n;i++) d[i]=0x3f3f3f3f,st[i]=0;
    d[s]=0;
    priority_queue<PII,vector<PII> ,greater<PII> > heap;
    heap.push(make_pair(0,s));
    while(heap.size()){
        auto t=heap.top();
        int ver=t.second,distance=t.first;
        if(st[ver]) continue;
        st[ver]=1;
        heap.pop();
        for(register int i=h[ver];i!=-1;i=ne[i]){
            int j=e[i];
            if(d[j]>w[i]+distance){
                d[j]=w[i]+distance;
                heap.push(make_pair(d[j],j));
            }
        }
    }
}
inline void Dijkstra1(int s){
    for(register int i=1;i<=n;i++) d1[i]=0x3f3f3f3f,st1[i]=0;
    d1[s]=0;
    priority_queue<PII,vector<PII> ,greater<PII> > heap;
    heap.push(make_pair(0,s));
    while(heap.size()){
        auto t=heap.top();  
        heap.pop();
        int ver=t.second,distance=t.first;
        if(st1[ver]) continue;
        st1[ver]=1;
        for(register int i=h1[ver];i!=-1;i=ne1[i]){
            int j=e1[i];
            if(d1[j]>w1[i]+distance){
                d1[j]=w1[i]+distance;
                heap.push(make_pair(d1[j],j));
            }
        }
    }
}
signed main(){
    scanf("%lld%lld",&n,&m);
    for(register int i=1;i<=2*m+10;i++){
        h[i]=-1;
        h1[i]=-1;
    }
    while(m--){
        int a,b,w;
        scanf("%lld%lld%lld",&a,&b,&w);
        add(a,b,w);
        add1(b,a,w);
    }
    Dijkstra(1);
    for(register int i=1;i<=n;i++) ans+=d[i];
    Dijkstra1(1);
    for(register int i=1;i<=n;i++) ans+=d1[i];
    printf("%lld",ans);
    return 0;
}

by DicaprioD @ 2024-10-21 07:53:14

@pengbonan 过了!!!!

感谢大佬 orz orz orz orz

洛谷还是好人多啊


by DicaprioD @ 2024-10-21 07:54:39

@gavinliu266 感谢大佬,这么改了真过了,但我太菜了,这么改有什么说法啊???

orz orz orz


by gavinliu266 @ 2024-10-21 18:08:43

如果当前已经 vis,那么将会无限循环(因为没有出队)。

因为堆不能修改,所以当有多个节点同时在优先队列中时,应当只算一次,剩下的全部出队(即先出队再判),这样就是正确的。

@DicaprioD


by DicaprioD @ 2024-10-21 19:01:49

@gavinliu266

搜嘎寺内,感谢佬


上一页 |