NOIP2014 寻找道路
陈子骏
2018-10-16 16:28:38
题目大意：
在有向图G 中，每条边的长度均为1 ，现给定起点和终点，请你在图中找一条从起点到终点的路径，该路径满足以下条件：
1 ．路径上的所有点的出边所指向的点都直接或间接与终点连通。
2 ．在满足条件1 的情况下使路径最短。
Solution
首先，预处理，把每条边反向。
从终点开始bfs，标记从终点开始可以走到的点。
第二步，枚举每一个点，如果这个点没有被标记，则枚举它的每一条出边（反向后的），如果它指向的点被标记，则说明这个被标记的点不合法，删除。
第三步，在合法点上bfs，单源最短路。找到答案
```
#include<bits/stdc++.h>
using namespace std;
int n,m;
struct edg{
int next,to;
}edge[200001];
edg hhhh[200001];
int head[200001],hed[200001];
int cnt,qwq;
int sec_ve[200001];
int ve[20001];
int vis[20001],dis[20001];
void add(int a,int b)
{
edge[++cnt].to=b;
edge[cnt].next=head[a];
head[a]=cnt;
hhhh[cnt].to=a;
hhhh[cnt].next=hed[b];
hed[b]=cnt;
}
int s,t;
int x,y;
queue<int>q;
queue<int>k;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)dis[i]=9999;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
if(x!=y)add(x,y);
}
scanf("%d%d",&s,&t);
k.push(t);
ve[t]=1;
while(!k.empty())
{
int u=k.front();
k.pop();
for(int i=hed[u];i;i=hhhh[i].next)
{
int v=hhhh[i].to;
if(!ve[v]){
ve[v]=1;
k.push(v);
}
}
}
for(int i=1;i<=n;i++)if(!ve[i])
for(int e=hed[i];e;e=hhhh[e].next)
sec_ve[hhhh[e].to]=true;
for(int i=1;i<=n;i++)vis[i]=0;
dis[s]=0;
q.push(s);
vis[s]=1;
while(!q.empty())
{
int u=q.front();
q.pop();
vis[u]=0;
if(!ve[u]||sec_ve[u])continue;
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].to;
if(dis[v]>dis[u]+1){
dis[v]=1+dis[u];
if(!vis[v])
{
vis[v]=1;
q.push(v);
}
}
}
}
if(dis[t]<9999)printf("%d",dis[t]);
else printf("-1");
}
```