这个程序数据一直过不了,求改
寻找道路(road.cpp)
【问题描述】
在有向图 G 中, 每条边的长度均为 1, 现给定起点和终点, 请你在图中找一条从起点到终点的路径,该路径满足以下条件: 1.路径上的所有点的出边所指向的点都直接或间接与终点连通。 2. 在满足条件 1 的情况下使路径最短。 注意:图 G 中可能存在重边和自环, 题目保证终点没有出边。 请你输出符合条件的路径的长度。
【输入】
第一行有两个用一个空格隔开的整数 n 和 m,表示图有 n 个点和 m 条边。
接下来的 m 行每行 2 个整数 x、 y,之间用一个空格隔开,表示有一条边从点 x 指向点 y。
最后一行有两个用一个空格隔开的整数 s、 t,表示起点为 s,终点为 t。
【输出】
输出只有一行, 包含一个整数, 表示满足题目描述的最短路径的长度。如果这样的路 径不存在,输出 -1。
【输入输出样例】
输入样例:
6 6
1 2
1 3
2 6
2 5
4 5
3 4
1 5
输出样例:
3
【输入输出样例说明】
如上图所示, 满足条件的路径为 1->3->4->5。 注意点 2 不能在答案路径中, 因为点 2连了一条边到点 6, 而点 6 不与终点 5 连通。
【数据说明】
对于 30%的数据, 0 < n ≤ 10, 0 < m ≤ 20;
对于 60%的数据, 0 < n ≤ 100, 0 < m ≤ 2000;
对于 100%的数据, 0 < n ≤ 10,000, 0 < m ≤ 200,000, 0 < x,y,s, t ≤ n, x ≠ t。
这是我的代码
#include <bits/stdc++.h>
#define N 10010
using namespace std;
int n,m;
bool flag=false;
int first,last;
bool vis[N]={0};
int deep[N]={0};
queue <int> q;
vector <int> a[N];
vector <int> b[N];
void dfs(int p){
vis[p]=1;
for(int i=0;i<b[p].size();i++){
int t=b[p][i];
if(!vis[t]) dfs(t);
}
}
void add(){
for(int i=1;i<=n;i++){
if(vis[i]==0){
for(int j=0;j<b[i].size();j++){
vis[b[i][j]]=0;
}
}
}
}
void bfs(){
memset(deep,0,sizeof(deep));
q.push(first);
deep[first]=0;
while(q.size()){
int x=q.front();
q.pop();
if(x==last){
cout<<deep[x]<<endl;
flag=true;
break;
}
for(int i=0;i<a[x].size();i++){
int y=a[x][i];
if(!deep[y] && vis[y]!=0){
q.push(y);
deep[y]=deep[x]+1;
}
}
}
}
int main(){
cin>>n>>m;
int x,y;
for(int i=1;i<=m;i++){
cin>>x>>y;
a[x].push_back(y);
b[y].push_back(x);
}
cin>>first>>last;
dfs(last);
add();
vis[last]=1;
bfs();
if(flag==false) cout<<-1<<endl;
return 0;
}