RT,最短路使用堆优化dj,尝试减少使用了几个数组但是无济于事,求大佬指点
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=10005;
vector<int> to[N];
vector<int> to2[N];
struct node{
int dis,pos;
bool operator <(const node &x)const {return x.dis<dis;}
};
priority_queue<node> q;
int n,m,st,en,cnt;
bool vis2[N],flag[N];
int dist[N];
void dfs2(int x){
vis2[x]=1;
for(int i=0;i<to2[x].size();i++){
dfs2(to2[x][i]);
}
}
void dijkstra(){
dist[st]=0;
vis2[st]=1;
q.push((node){0,st});
while(!q.empty()){
node t=q.top();q.pop();
int x=t.pos;
for(int i=0;i<to[x].size();i++){
int y=to[x][i];
if(flag[y]) continue;
if(dist[y]>dist[x]+1){
dist[y]=dist[x]+1;
if(!vis2[y]){
vis2[y]=1;
q.push((node){dist[y],y});
}
}
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
if(x==y) continue;
to[x].push_back(y);
to2[y].push_back(x);
}
scanf("%d%d",&st,&en);
dfs2(en);
for(int i=1;i<=n;i++){
if(vis2[i]) continue;
flag[i]=1;
for(int j=0;j<to2[i].size();j++) flag[to2[i][j]]=1;
}
for(int i=1;i<=n;i++) dist[i]=inf;
for(int i=1;i<=n;i++) vis2[i]=0;
dijkstra();
if(dist[en]==inf) printf("-1\n");
else printf("%d\n",dist[en]);
return 0;
}