大佬们,帮我看看为什么9个点MLE,我内存开的也不多呀。
查看原帖
大佬们,帮我看看为什么9个点MLE,我内存开的也不多呀。
299711
单调欧文楼主2021/3/21 11:10
#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
struct node{
	int t;
	int w;
};
int n,m;
int st,en;
vector<int> adj[10001];
priority_queue<node,vector<node>,greater<node> > q;
bool operator >(node a,node b){
	return a.w < b.w;
}

int dis[10001],r[10001];
void bfs(int s){
	for(int i = 0; i < adj[s].size(); i++){
			int to = adj[s][i];
			r[to]--;
			bfs(to);
	}
}

void dijkstra(){
	memset(dis,0x3f,sizeof(dis));
	dis[en] = 0;
	q.push(node{en,dis[en]});
	while(!q.empty()){
		int k = q.top().t;
		int v = q.top().w;
		q.pop();
		if(v != dis[k]) break;
		for(int i = 0; i < adj[k].size(); i++){
			int to = adj[k][i];
			if(r[to] > 0) continue;
			if(dis[to] > dis[k] + 1){
				dis[to] = dis[k] + 1;
				q.push(node{to,dis[to]});
			}
		} 
	}
	if(dis[st] == dis[0]) cout << -1 << endl;
	else cout << dis[st];
}
int main(){
	cin >> n >> m;
	for(int i = 1; i <= m; i++){
		int u,v;
		cin >> u >> v;
		r[u]++;
		adj[v].push_back(u);
	}
	cin >> st >> en;
	bfs(en);
	dijkstra();
	
	
	
	return 0;
}

爸爸们,帮帮忙呀,祖宗们,行行好吧

2021/3/21 11:10
加载中...