寻找道路
题目描述:
有点的出边所指向的点都直接或间接与终点连通。
2 ．在满足条件1 的情况下使路径最短。
注意：图G 中可能存在重边和自环，题目保证终点没有出边。
请你输出符合条件的路径的长度。
输入格式:
第一行有两个用一个空格隔开的整数n 和m ，表示图有n 个点和m 条边。
接下来的m 行每行2 个整数x 、y ，之间用一个空格隔开，表示有一条边从点x 指向点y 。
最后一行有两个用一个空格隔开的整数s 、t ，表示起点为s ，终点为t 。
输出格式:
输出只有一行，包含一个整数，表示满足题目᧿述的最短路径的长度。如果这样的路径不存在，输出- 1 。
样例输入:
样例1： 3 2 1 2 2 1 1 3 样例2： 6 6 1 2 1 3 2 6 2 5 4 5 3 4 1 5
样例输出:
样例1： -1样例2： 3
提示:
解释1：
如上图所示，箭头表示有向道路，圆点表示城市。起点1 与终点3 不连通，所以满足题
目᧿述的路径不存在，故输出- 1 。
解释2：
如上图所示，满足条件的路径为1 - >3- >4- >5。注意点2 不能在答案路径中，因为点2连了一条边到点6 ，而点6 不与终点5 连通。
对于30%的数据，0
对于60%的数据，0
对于100%的数据，0
时间限制:1000ms
空间限制:256MByte
来源:NOIP2014提高t5
俗话说的好啊，现有搜索后有天，反向剪枝日神仙。这题在网上的题解十分多我看了一下，有用栈优化bellman-ford，SPFA，Dijkstra+heap，bellman-ford+stack等等等等，这些我都听不懂。呆滞大佬说，我只要两次bfs就可以搞定。关于程序中诡异的ti数组和a结构体，详见《联合权值——呆滞大佬der最骚操作？》
http://www.cnblogs.com/cain-/p/7306003.html
#include<bits/stdc++.h>
#include<bits/stdc++.h>
using namespace std;
struct nob{int sta,ed;
}a[200005];
bool mmp(nob a,nob b){return a.ed<b.ed;
}
int n,m,has[100005]={0},has1[100005]={0},s[1000001]={0},ti[200005]={0},start,finish,step[200005]={0};
int main(){cin>>n>>m;for (int i=1; i<=m; i++){cin>>a[i].sta>>a[i].ed;ti[a[i].ed]++;}//这里是不是觉得有点奇怪for (int i=1; i<=n; i++) ti[i]+=ti[i-1];cin>>start>>finish;sort(a+1,a+1+m,mmp);int head=0,tail=1;s[1]=finish;//从尾巴开始找has[finish]=1;while (head<tail){head++;for (int i=ti[s[head]-1]+1; i<=ti[s[head]]; i++){if (has[a[i].sta]==0){has[a[i].sta]=1;tail++;s[tail]=a[i].sta;}}}//找出不能到达的点for (int i=1; i<=n; i++){if (has[i]==0){has1[i]=1;for (int l=ti[i-1]+1; l<=ti[i]; l++){has1[a[l].sta]=1;}}}//用不能到达的点来反向标记他的父亲，表示父亲节点有子节点没有直接或间接地指向终点head=0;tail=1;s[1]=finish;has1[finish]=1;while (head<tail){head++;if (s[head]==start){cout<<step[s[head]];return 0;}for (int i=ti[s[head]-1]+1; i<=ti[s[head]]; i++){if (has1[a[i].sta]==0){has1[a[i].sta]=1;tail++;s[tail]=a[i].sta;step[a[i].sta]=step[a[i].ed]+1;}}}//再次广搜找出答案cout<<-1;return 0;
}
参考了联合权值那道题目之后你会发现这个有些奇怪，那就对了，这就是传说中最难以预判的剪枝，倒搜剪枝！用正着搜索的话即使用同样的方法还是过不了的，然后我们再来仔细地研究一下这个代码，就会发现这里用了两次广搜，第一次广搜看上去是将能够到达的点标记，实质上是遍历has数组将不能到达的点找出来，找到不能到达的点之后再在has1数组中将他的父亲节点和他自己标记起来表示这些点不能走。然后就可以完成这道题目啦。
made by cain-
