堆优化 T 飞了,求助
  • 板块P1342 请柬
  • 楼主DicaprioD
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/4/29 18:51
  • 上次更新2024/4/29 20:39:29
查看原帖
堆优化 T 飞了,求助
946114
DicaprioD楼主2024/4/29 18:51

只过了第 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;
}
2024/4/29 18:51
加载中...