niop 2014寻找道路

时间:2024-10-12 14:36:19
/*
乍一看就是个最短路 SFPA
但是要保证路径上的所有点的出边所指向的点都直接或间接与终点连通。
这一点就蛋疼了0.0
开始想的是正着跑一边 每一个点的所有边都能符合条件 那这个点就符合条件0.0 可惜WA +RE 了
后来xyd大神说 可以先到这从终点跑一边 能到的标记 然后在枚举每个点的所有边指向的点 全被标记那么这个点就ok
最后SPFA
注意 正反建边 数组要大!!!!!!!!
还有 从终点跑一边 能到的标记时Dfs会TLE 所以0.0 BFs了
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define maxn 10010
#define maxx 400010
using namespace std;
queue<int>q;
int n,m,head1[maxx],head2[maxx],num,s,t,f[maxn],ans[maxn],cn1[maxn],cn2[maxn];
struct node
{
int v,dis,pre;
}e1[maxx],e2[maxx];
/*int Dfs(int p)
{
f[p]=1;
for(int i=head2[p];i;i=e2[i].pre)
{
cn1[e2[i].v]=1;
if(f[e2[i].v]==0)
Dfs(e2[i].v);
}
}*/
void Bfs(int p)
{
q.push(p);
f[p]=;
int i;
while(!q.empty())
{
int k=q.front();
q.pop();
for(i=head2[k];i;i=e2[i].pre)
{
cn1[e2[i].v]=;
if(f[e2[i].v]==)
{
q.push(e2[i].v);
f[e2[i].v]=;
}
}
}
}
void Biu()
{
int i,j;
for(i=;i<=n;i++)
{
int g=;
for(j=head1[i];j;j=e1[j].pre)
if(cn1[e1[j].v]==)
g=;
if(g==)
cn2[i]=;
}
}
int main()
{
scanf("%d%d",&n,&m);
int i,x,y;
memset(ans,,sizeof(ans));
for(i=;i<=m;i++)
{
scanf("%d%d",&x,&y);
num++;
e1[num].v=y;
e1[num].dis=;
e1[num].pre=head1[x];
head1[x]=num;
num++;
e2[num].v=x;
e2[num].dis=;
e2[num].pre=head2[y];
head2[y]=num;
}
scanf("%d%d",&s,&t);
Bfs(t);
cn1[t]=;
Biu();
memset(f,,sizeof(f));
q.push(s);
ans[s]=;
f[s]=;
while(!q.empty())
{
int k=q.front();
q.pop();
f[k]=;
for(i=head1[k];i;i=e1[i].pre)
if(ans[e1[i].v]>ans[k]+e1[i].dis&&cn2[k]==)
{
ans[e1[i].v]=ans[k]+e1[i].dis;
if(f[e1[i].v]==)
{
q.push(e1[i].v);
f[e1[i].v]=;
}
}
}
if(ans[t]<0x7fffffff)printf("%d",ans[t]);
else printf("-1");
return ;
}