堆优化 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 gavinliu266 @ 2024-04-29 19:12:26

你在更新答案时判断 vis 了吗?要判断的。


by pengbonan @ 2024-10-20 20:25:24

@gavinliu266

        if(st1[ver]) continue;
        st1[ver]=1;

判了啊


by gavinliu266 @ 2024-10-20 20:29:46

if(d1[j]>w1[i]+distance){
    d1[j]=w1[i]+distance;
    heap.push(make_pair(d1[j],j));
}

应为

if(!stl[j] && d1[j]>w1[i]+distance){
    d1[j]=w1[i]+distance;
    heap.push(make_pair(d1[j],j));
}

可能是我写法的问题,有时不判会出错。

然后还有一个地方初始化无穷大不够大。

其它没看。

@pengbonan


by pengbonan @ 2024-10-20 20:33:34

@gavinliu266 0x3f3f3f3f 够大了吧


by pengbonan @ 2024-10-20 20:34:29

@gavinliu266 那里不用判吧


by gavinliu266 @ 2024-10-20 20:42:24

@pengbonan 可是最短路可能炸 int,所以 lz 把 int 定义为 long long,相应地,这里应该是 0x3f3f3f3f3f3f3f3f


by gavinliu266 @ 2024-10-20 20:42:41

可能确实不用判。


by gavinliu266 @ 2024-10-20 20:43:47

哦我明白了。

if(st[ver]) continue;
st[ver]=1;
heap.pop();

应为

heap.pop();
if(st[ver]) continue;
st[ver]=1;

by pengbonan @ 2024-10-20 21:11:02

@DicaprioD 修改一下试试


by DicaprioD @ 2024-10-21 07:47:47

@pengbonan 6个月前的帖子怎么突然活了

orz orz orz


| 下一页