TLE

评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 604 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 608 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 608 KiB, score = 10
测试数据 #3: TimeLimitExceeded, time = 1015 ms, mem = 600 KiB, score = 0
测试数据 #4: TimeLimitExceeded, time = 1015 ms, mem = 600 KiB, score = 0
测试数据 #5: TimeLimitExceeded, time = 1203 ms, mem = 600 KiB, score = 0
测试数据 #6: TimeLimitExceeded, time = 1015 ms, mem = 600 KiB, score = 0
测试数据 #7: TimeLimitExceeded, time = 1031 ms, mem = 608 KiB, score = 0
测试数据 #8: TimeLimitExceeded, time = 1015 ms, mem = 612 KiB, score = 0
测试数据 #9: TimeLimitExceeded, time = 1015 ms, mem = 612 KiB, score = 0
TimeLimitExceeded, time = 7309 ms, mem = 612 KiB, score = 30
代码
#include <algorithm>
#include <cstdio>
using namespace std;
int n,m,s,t,u[10001],v[10001];
bool vis[10001],g[10001];
inline bool _dfs(int now) {
  if (now == t) return true;
  for (int i = 1;i <= m;i++)
    if (u[i] == now && !vis[v[i]]) {
      vis[v[i]] = true;
      if (_dfs(v[i])) return true;
      vis[v[i]] = false;
    }
  return false;
}
int Min = 100000000;
inline void dfs(int now,int tot) {
  if (now == t) {
    Min = min(Min,tot);
    return;
  }
  for (int i = 1;i <= m;i++)
    if (u[i] == now && !vis[v[i]] && g[v[i]]) {
      vis[v[i]] = true;
      dfs(v[i],tot+1);
      vis[v[i]] = false;
    }
}
int main() {
  //freopen("road.in","r",stdin);
  //freopen("road.out","w",stdout);
  scanf("%d%d",&n,&m);
  for (int i = 1;i <= m;i++) scanf("%d%d",&u[i],&v[i]);
  scanf("%d%d",&s,&t);
  fill(g+1,g+n+1,true);
  for (int i = 1;i <= n;i++) {
    fill(vis+1,vis+n+1,false);
    bool temp = _dfs(i);
    if (!temp)
      for (int j = 1;j <= m;j++)
        if (v[j] == i) g[u[j]] = false;
  }
  fill(vis+1,vis+n+1,false);
  dfs(s,0);
  printf("%d",Min == 100000000 ? -1 : Min);
  return 0;
}

1 条评论

  • 1

信息

ID
1909
难度
7
分类
图结构 点击显示
标签
递交数
3977
已通过
885
通过率
22%
被复制
8
上传者