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