求改程序
  • 板块灌水区
  • 楼主Gnimnehs
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/1/8 21:55
  • 上次更新2024/1/9 12:53:48
查看原帖
求改程序
772337
Gnimnehs楼主2024/1/8 21:55

这个程序数据一直过不了,求改

寻找道路(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;
} 
2024/1/8 21:55
加载中...