这道题真的很女少啊

言归正传：

这道题其实就是考验的思路，读题后，我们发现对于某个点他所连接的点必须连接终点，那么我们直接反向存图，从终点进行bfs，可以找到未连接的点，然后对这些点所连接的点进行标记，最后来一遍最短路就OK了。

SPFA好啊

上代码：

#include <bits/stdc++.h>

using namespace std;

int n , m , s , ee;

int dis[10010] , vis[10010] , f[10010];

vector<int> e[10010];

vector<int> pd[10010];

void spfa(){

	queue<int> q;

	q.push(s);

	dis[s] = 0 , vis[s] = 0;

	int x;

	while(!q.empty()){

		x = q.front();

		q.pop();

		vis[x] = 1;	//spfa的时候需要这样重复更新

		for(int i = 0; i < e[x].size(); i++){

			int y = e[x][i];

			if(!vis[y]) continue;

			if(dis[x] + 1 < dis[y]){

				dis[y] = dis[x] + 1;

				if(vis[y]){

					vis[y] = 0;

					q.push(y);

				}

			}

		}

	}

}

void bfspd(){

	queue<int> q;

	f[ee] = 1;

	q.push(ee);

	int x;

	while(!q.empty()){

		x = q.front();

		q.pop();

		for(int i = 0; i < pd[x].size(); i++){

			int y = pd[x][i];

			if(!f[y]){

				f[y] = 1;

				q.push(y);

			}

		}

	}

}

int main(){

	cin >> n >> m;

	for(int i = 1; i <= 10010; i++) dis[i] = 0x3fffff;

	for(int i = 1; i <= m; i++){

		int x , y;

		cin >> x >> y;

		if(x == y) continue;	//重边

		e[x].push_back(y);

		pd[y].push_back(x);	//倒序存储，用终点来看可以到达的点

	}

	cin >> s >> ee;

	bfspd();

	for(int i = 1; i <= n; i++) vis[i] = f[i];	//因为f数组会改变，所以提前复制到另外一个数组

	for(int i = 1; i <= n; i++)

		if(!f[i])

			for(int j = 0; j < pd[i].size(); j++) if(vis[pd[i][j]]) vis[pd[i][j]] = 0;

	spfa();

	if(dis[ee] == 0x3fffff) cout << -1;

	else cout << dis[ee];

	return 0;

}

巴特西

洛谷 P2296 【寻找道路】

言归正传：

SPFA好啊

最新文章

热门文章