萌新初学OI,9 MLE求助
查看原帖
萌新初学OI,9 MLE求助
552578
又菜又爱玩楼主2022/10/3 15:34

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;
} 
2022/10/3 15:34
加载中...