紧急求调,即将破防
  • 板块题目总版
  • 楼主xpg007
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/6/8 20:59
  • 上次更新2024/6/8 22:36:19
查看原帖
紧急求调,即将破防
1024680
xpg007楼主2024/6/8 20:59

pts 50% WA

#include <bits/stdc++.h>
using namespace std;
vector<int> g1[10001];
vector<int> g2[10001];
vector<int> a1;
vector<int> a2;
bool vis1[10001], vis2[10001], vis3[10001], cvis[10001];
int cnt[10001];
void dfss(int x){
	if (vis1[x])
		return ;
	vis1[x] = true;
	a1.push_back(x);
	for (int i = 0; i < g1[x].size(); i++)
		dfss(g1[x][i]);
}
void dfst(int x){
	if (vis2[x])
		return ;
	vis2[x] = true;
	a2.push_back(x);
	for (int i = 0; i < g2[x].size(); i++)
		dfst(g2[x][i]);
}
void laji(int x){
	if (cvis[x])
		return ;
	cvis[x] = true;
	for (int i = 0; i < g2[x].size(); i++)
		laji(g2[x][i]);
}
bool unin(vector<int> v, int x){
	for (int i = 0; i < v.size(); i++)
		if (v[i] == x)
			return false;
	return true;
}
void init(){
	for (int i = 0; i < a2.size(); i++)
		if (unin(a2, a1[i]))
			laji(a1[i]);
}
int main(){
	int n, m, s, t;
	cin >> n >> m;
	for (int i = 1; i <= m; i++){
		int u, v;
		cin >> u >> v;
		g1[u].push_back(v);
		g2[v].push_back(u);
	}
	cin >> s >> t;
	dfss(s);
	dfst(t);
	init();
	cvis[s] = false, cvis[t] = false;
	queue<int> q;
	q.push(s);
	cvis[s] = true;
	while (!q.empty()){
		int r = q.front();
		q.pop();
		if (r == t){
			cout << cnt[r];
			return 0;
		}
		for (int i = 0; i < g1[r].size(); i++)
			if (!cvis[g1[r][i]]){
				cvis[g1[r][i]] = true;
				cnt[g1[r][i]] = cnt[r] + 1;
				q.push(g1[r][i]);
			}
	}
	cout << -1;
	return 0;
}

想要死掉,调了1小时了

2024/6/8 20:59
加载中...