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
搜嘎寺内,感谢佬