题解 P2296 【寻找道路】

yyy2015c01 · 2016-02-24 23:10:02 · 题解

思路详见：http://iyyy.sinaapp.com/?p=765

#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<vector>
const int N=200001;
using namespace std;
struct wxy
{
 int point,k;
};
wxy newpush(int point,int k)
{
 wxy temp;
 temp.point = point;
 temp.k = k;
 return temp;
}
vector <int> map[N];//邻接表的建立
wxy mdzz[2*N]={0};
int head=0,tail=1;//搜索队列 
int n,m,s,t;
bool _able[N]= {false},able[N]= {false};
int main()
{
 scanf("%d %d",&n,&m);
 for (int i=1,x,y; i<=m; i++)
 {
 scanf("%d %d",&x,&y);
 map[y].push_back(x);//反着存图以便从终点爆肝
 }
 scanf("%d %d",&s,&t);
 //输入完毕
 mdzz[tail]=newpush(t,0);
 while(head<=tail)//bfs，找出无法访问的废点
 {
 wxy now=mdzz[head++];
 able[now.point]=true;
 for (int i=0; i<map[now.point].size(); i++)
 if (!able[map[now.point][i]])
 {
 mdzz[++tail]=newpush(map[now.point][i],now.k+1);
 }
 }
 /*for (int i=0;i<=3;i++)
 cout<<_able[i]<<" ";*/
 for (int i=0; i<=n; i++)
 _able[i]=able[i];
 for (int i=1; i<=n; i++) //排除点
 if (!_able[i])
 for (int j=0; j<map[i].size(); j++)
 able[map[i][j]] = false;//把废点的父节点筛去
 //可选点筛选完毕
 head=0;
 tail=1;
 mdzz[tail]=newpush(t,0);
 while(head<=tail) //bfs寻找最短路径
 {
 wxy now=mdzz[head++];
 if (!able[now.point]) 
 continue;
 for (int i=0; i<map[now.point].size(); i++)
 if (map[now.point][i]!=t)
 {
 mdzz[++tail]=newpush(map[now.point][i],now.k+1);
 if (map[now.point][i] == s)
 {
 printf("%d\n",now.k+1);
 return 0;
 }
 }
 }
 printf("-1\n");
 //获得成就[编写完成] 
 return 0;
}