- 寻找道路
- 2016-11-08 17:03:26 @
评测结果
编译成功
测试数据 #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 条评论
-
唐复之 LV 8 @ 2016-11-08 20:45:08
万能的搜索!!!
- 1