这个是我最开始写的 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 了,空间应该没开错吧,请问这是什么原因?