求救!!!样例全过,只有十分!!!
查看原帖
求救!!!样例全过,只有十分!!!
262321
_CMJ楼主2021/6/5 14:21

请大佬们看看:

#include <bits/stdc++.h>

using namespace std;

const int KMaxN = 10001;

bool b[KMaxN], b1[KMaxN];
int n, m;
int s, t;
bool zzh;
int num;
int f[KMaxN];
int vis[KMaxN];

struct node {
  queue<int> q, q1, fa;
  int chu;
  int ru;
} a[KMaxN];

inline bool work(int ans[], int x) {
  for (int i = 1; i <= x; i++) {
    while(!a[i].q1.empty()) {
      int g = a[i].q1.front();
      a[i].q1.pop();
      if (!vis[g]) return false;
    }
  }
  return true;
}

inline void bfs(int ccc) {
  if (vis[ccc] == true) return;
  vis[ccc] = true;
  while(!a[ccc].fa.empty()) {
    int g = a[ccc].fa.front();
    a[ccc].fa.pop();
    bfs(g);
  }
  return;
}

inline void dfs(int dep, int step, int ans[], int x) {
  if (dep == t && work(ans, x)) {
    num = min(step, num);
    return;
  }
  if (b[dep] == true)return;
  if (a[dep].chu == 0 && dep != t) return;
  ans[x] = dep;
  x++;
  while(!a[dep].q.empty()) {
    int g = a[dep].q.front();
    a[dep].q.pop();
    b[dep] = true;
    dfs(g, step + 1, ans, x);
    b[dep] = false;
  }
  return;
}

int main() {
  num = 0x3f3f3f;
  zzh = 0;
  memset(b, false, sizeof(b));
  memset(f, 0, sizeof(f));
  memset(b1, false, sizeof(b1));
  memset(vis, false, sizeof(vis));
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
	  int x, y;
	  cin >> x >> y;
	  a[x].q.push(y);
	  a[x].q1.push(y);
	  a[y].fa.push(x);
	  a[x].chu++, a[y].ru++;
  }
  cin >> s >> t;
  bfs(t);
  if (a[t].ru == 0) {
    cout << -1 << endl;
    return 0;
  }
  dfs(s, 0, f, 1);
  if (num == 0x3f3f3f3f3f3f) {
    cout << -1 << endl;
  } else {
    cout << num << endl;
  }
	return 0;
}
/*
6 6
1 2
1 3
2 6
2 5
4 5
3 4
1 5
*/
2021/6/5 14:21
加载中...