题解 P2296 【寻找道路】
不知道有没有人这样做，发一篇题解看看能不能过
本蒟蒻刚开始看这题以为就是一个最短路的板子，于是欢快的打了一个dijkstra
嗯好的第一个样例过了，心想这题真是太水了
结果到了第二个数据就懵住了，嗯怎么输出的是2？
再一看样例解释就找到问题了，如果当前找到的最短路上有一个点指向一个不与终点相连的点，那么此路不通，就找第二短的路，以此类推
如果都不能走，输出-1即可
然后本蒟蒻就把dijkstra反着跑了一遍尝试找出所有不和终点相连的点标记一下，再把与该点（即不与终点相连的点）相连的点也标记一遍，标记过的点在第二遍dijkstra时不能走（当然起点肯定可以走）
嗯大概就是这样，由于本蒟蒻太蒟蒻了，所以代码很冗杂......
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int INF=2147483647;
const int N=6000001;
const int M=10001;
int cnt=1;
int to[N],nxt[N],head[N],dis[N],vis[N],a[N],b[N],frog[N];
ll bi[N];
int n,m,s,t;
struct node
{
int dis,pos;
bool operator <(const node &x)const
{
return x.dis<dis;
}
};
void qxx(int x,int y)
{
to[++cnt]=y;
nxt[cnt]=head[x];
head[x]=cnt;
}
priority_queue<node> q;
void dijkstra()
{
dis[t]=0;
q.push((node){0,t});
while(!q.empty())
{
node k=q.top();
q.pop();
int x=k.pos;
if(vis[x])
continue;
vis[x]=1;
for(register int i=head[x];i;i=nxt[i])
{
int kk=to[i];
if(dis[kk]>dis[x]+1)
{
dis[kk]=dis[x]+1;
if(!vis[kk])
q.push((node){dis[kk],kk});
}
}
}
}
void dijkstra1()
{
dis[s]=0;
q.push((node){0,s});
while(!q.empty())
{
node k=q.top();
q.pop();
int x=k.pos;
if(vis[x]||!frog[x])
continue;
vis[x]=1;
for(register int i=head[x];i;i=nxt[i])
{
int kk=to[i];
if(dis[kk]>dis[x]+1)
{
dis[kk]=dis[x]+1;
if(!vis[kk])
q.push((node){dis[kk],kk});
}
}
}
}
void init()//初始化
{
memset(head,0,sizeof(head));
cnt=1;//不要问我为什么是1，随便给一个数都可以
memset(vis,0,sizeof(vis));
memset(dis,63,sizeof(dis));
}
void dfs()//寻找与不与终点相连的点相连的点并标记
{
memset(frog,1,sizeof(frog));//不要在意这个frog qwq
for(register int i=1;i<=n;i++)
{
if(!bi[i])
{
for(register int j=head[i];j;j=nxt[j])
{
int kk=to[j];
frog[kk]=0;
}
}
}
frog[s]=1;
}
int main()
{
scanf("%d%d",&n,&m);
init();
for(register int i=1;i<=n;i++)
{
dis[i]=INF;
}
for(register int i=1;i<=m;i++)
{
scanf("%d%d",&a[i],&b[i]);
qxx(b[i],a[i]);//反向跑肯定要反着建边
}
scanf("%d%d",&s,&t);
dijkstra();//反着跑
for(register int i=1;i<=n;i++)
{
if(!vis[i])
bi[i]=0;
else bi[i]=1;//如果反着跑能跑到就说明这个点和终点相连
}
dfs();
init();
for(register int i=1;i<=m;i++)
qxx(a[i],b[i]);
dijkstra1();
if(dis[t]==dis[0])//没有跑到终点
printf("-1");//输出-1
else printf("%d",dis[t]);
return 0;
}