题解 P2296 【寻找道路】
空の軌跡
2019-05-30 18:55:48
# 写在前面：
很好的思路题，当您长时间思考而无解时再来看本篇题解，请务必独立认真思考。当然您也可以把本篇题解来与您的思路进行对比进行自我能力的提升。
### 独上高楼，望尽天涯路。
------------
# 步入正题：
## 通过思考，可以看出：
题目中的点可以分为三种：
① 自己指向的节点都可以到达终点。
② 自己可以到达终点的点。
③ 普通的点。
### 那么题目需要的就是：
由①组成的连接了起点和终点的最短路径。
# 思路：
显然③包含②，②包含①。
那么我们就先通过③求出所有的②，再通过②求出①。
最后再来一遍BFS就能求出最短路径了。
#### update 2019.11.06 :
感谢 @WestTree 的 HACK 数据
~~~
4 6
4 2
4 4
1 1
1 4
1 1
1 3
1 3
~~~
这组数据中起点本身不符合条件 ① ，所以原先的代码未判定起点就直接入队是错误的。现已更正。
## 步骤：
#### 1.读入数据，并建立正向和反向边。
#### 2.从终点反向BFS，求出所有的②。
#### 3.对每个点判断是否满足①。
#### 4.从起点正向BFS，只经过①点，求出最短路径。
## 数组解释：
#### 1.inroad 表示是否为 ①
#### 2.can 表示是否为 ②
#### 3.dis 表示距离起点的距离，计算长度用，
#### 4.side 正向边
#### 5.edis 反向边
# 总结：
对于这种类型图论题，如果答案仅与终点有关的话，那么建反向边跑反向图的思路是十分高效并且好理解的，代码实现也很容易。
仅有一个终点，而不知起点。那么显然任意路径都会将终点作为路径上的一个必然点。利用所有路径的这个通性，改变思路，转而走反向图，就能改为从 **已知的起点** , 走到 **未知的终点** 了。
_**未知的起点，确定的终点**_。如果枚举起点跑到终点的话自然不优，所以我们可以将条件转换，从已经确定好的终点反向查找起点，复杂度就会下降很多。这就是我对这类题的经验。
# 代码：
80行，有点长。如果你大括号换行并且再压压行，60行能搞定。
~~~cpp
#include<iostream>
#include<vector>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
bool inroad[10010],can[10010]; //inroad 表示此点是否可以出现在路径上 can 表示此点是否可以到达终点
int dis[10010]; //dis 表示此点距离起点的距离
vector<int>side[10010]; //正向建边
vector<int>edis[10010]; //反向建边
int main()
{
int n,m,a,b,s,t;
cin>>n>>m;
for(int i=1;i<=m;i++) //读入并正反向建边
{
cin>>a>>b;
side[a].push_back(b);
edis[b].push_back(a);
}
cin>>s>>t;
can[t]=1; //终点先设置为 1
queue<int>que;
que.push(t);
while(!que.empty()) //从终点反向查找②
{
int now=que.front();
que.pop();
for(int i=edis[now].size()-1;i>=0;i--)
{
int to=edis[now][i];
if(!can[to])
{
que.push(to);
can[to]=1;
}
}
}
if(!can[s]) //起点无法到达终点就直接结束程序
{
cout<<"-1";
return 0;
}
for(int i=1;i<=n;i++) //判断哪些点是①
{
if(can[i])
{
inroad[i]=1;
for(int j=side[i].size()-1;j>=0;j--) //遍历所有的边
{
int to=side[i][j];
if(!can[to]) //如果它出边所到达的点无法到达终点,这个点就不可以出现在路径上
{
inroad[i]=0;
break;
}
}
}
}
if(!inroad[s]) //这里需要特殊判定一下起点是否满足条件，感谢 @WestTree 的HACK
{
cout<<"-1";
return 0;
}
dis[s]=1;que.push(s);
while(!que.empty()) //从起点bfs，只经过①点，找出最短距离
{
int now=que.front();
que.pop();
if(now==t) //到达终点,输出结果
{
cout<<dis[t]-1;
return 0;
}
for(int i=side[now].size()-1;i>=0;i--)
{
int to=side[now][i];
if(inroad[to]&&!dis[to])
{
dis[to]=dis[now]+1;
que.push(to);
}
}
}
cout<<"-1"; //否则还是无法到达
}
~~~
## 独自莫凭栏，无限江山。别时容易见时难！
### ~~如果看了这篇题解后有收获，希望您不要吝啬点赞！~~