求助!
查看原帖
求助!
767295
hfjqwq楼主2023/8/13 21:01

这个是我最开始写的 Dijkstra + 堆优化 的最短路代码,注意这里数组开的空间 maxn=2507,maxm=6207;,然后莫名奇妙 WA、TLE 了一个点,记录

#include<bits/stdc++.h>
#define endl '\n'
const int inf=0x3f3f3f3f,maxn=2507,maxm=6207;
using namespace std;
int n,m,s,t;
int head[maxn],nxt[maxm],weight[maxm],to[maxm],tot,dis[maxn];
bool inq[maxn];
priority_queue<pair<int,int> > q;
int read(){
	int ret=0,sgn=0; char ch=getchar();
	while(!isdigit(ch)) sgn |= ch == '-', ch = getchar();
	while(isdigit(ch)) ret = ret*10 + ch-'0', ch = getchar();
	return sgn ? -ret : ret;
}
void add(int u,int v,int w){
	to[++tot]=v;
	nxt[tot]=head[u];
	head[u]=tot;	
	weight[tot]=w;
}
void Dijkstra(){
	memset(dis,0x3f,sizeof(dis));
	dis[s]=0;
	q.push(make_pair(0,s));
	while(q.size()){
		int now=q.top().second; q.pop();
		if(inq[now]) continue;
		inq[now]=true;
		for(int i=head[now];i;i=nxt[i]){
			int af=to[i];
			if(dis[now]+weight[i]<dis[af]){
				dis[af]=dis[now]+weight[i];
				q.push(make_pair(-dis[af],af));
			}
		}
	}
}
int main(){
	n=read(); m=read(); s=read(); t=read();
	for(int i=1;i<=m;i++){
		int u,v,w;
		u=read(); v=read(); w=read();
		add(u,v,w); add(v,u,w);
	}
	Dijkstra();
	cout<<dis[t]<<endl;
	return 0;
}

而我后面把空间 改成 maxn=25007,maxm=62007 就 AC 了,空间应该没开错吧,请问这是什么原因?

2023/8/13 21:01
加载中...