MLE求助
查看原帖
MLE求助
271096
Semorius楼主2021/11/17 08:24
#include <bits/stdc++.h>
using namespace std;
const int SIZE = 10005;
int n, m;
vector<int> e[SIZE], e1[SIZE];
bool v[SIZE], vv[SIZE];
int s, t;
int d[SIZE];
bool vis[SIZE];
priority_queue< pair<int, int> > q;

inline int rd(){
	int x = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9'){
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9'){
		x = (x<<1)+(x<<3)+(ch^48);
		ch = getchar();
	}
	return x*f;
}

void dfs1(int x){
	v[x] = 1;
	for(int i = 0; i < e1[x].size(); i++){
		int y = e1[x][i];
		if(v[y]) continue;
		dfs1(y);
	}
}

void dfs2(int x){
	bool flag = true;
	for(int i = 0; i < e[x].size(); i++){
		int y = e[x][i];
		if(!v[y]){
			flag = false;
			continue;	
		} 
		dfs2(y);
	}
	if(!flag) vv[x] = 0;
}

void dij(int st){
	memset(d, 0x3f, sizeof(d));
	q.push(make_pair(0, st)); d[st] = 0;
	while(q.size()){
		int x = q.top().second; q.pop();
		if(vis[x]) continue;
		vis[x] = true;
		for(int i = 0; i < e[x].size(); i++){
			int y = e[x][i];
			if(!vv[y]) continue;
			if(d[x] + 1 < d[y]){
				d[y] = d[x] + 1;
				q.push(make_pair(-d[y], y));
			}
		}
	}
}

int main() {
	n = rd(), m = rd();
	for(int i = 1; i <= m; i++){
		int x = rd(), y = rd();
		e1[y].push_back(x); e[x].push_back(y);
	}
	s = rd(), t = rd();
	dfs1(t);
	for(int i = 1; i <= n; i++) vv[i] = v[i];
	dfs2(s);
	if(!vv[s]){
		printf("-1");
		return 0;
	}
	dij(s);
	if(d[t] > m) printf("-1");
	else printf("%d", d[t]);
	return 0;
}

2021/11/17 08:24
加载中...