两边spfa10
www
我的oi2014交代了

const nn=10000;
var
m,n,x,y,s,t,tn,h,tt,i,j,k:longint;
map:array[1..nn,1..nn]of boolean;
f,de:array[1..nn]of boolean;
q:array[0..nn]of integer;
ans:int64;

begin
readln(n,m); ans:=0;
fillchar(f,sizeof(f),false);
fillchar(map,sizeof(map),false);
fillchar(de,sizeof(de),false);
for i:=1 to m do begin readln(x,y);map[x,y]:=true; end;
readln(s,tn);
for i:=1 to n do if(i<>tn)and(not de[i])then
begin
for k:=1 to n do
if map[i,k] then
begin f[i]:=true;break; end;
if not f[i] then
for j:=1 to n do
if map[j,i] then
begin de[j]:=true;f[j]:=false;map[j,i]:=false; end;
end;
f[tn]:=true;h:=0;t:=1;q[t]:=s;
while h<>t do
begin
tt:=t; inc(ans);
while h<>tt do
begin
h:=(h+1)mod nn; x:=q[h];
for i:=1 to n do
if f[i] then if map[x,i] then
begin
if i=tn then
begin
writeln(ans);halt;
end;
t:=(t+1)mod nn;q[t]:=i;f[i]:=false;
end;
end;
end;
writeln(-1);
end.
比赛ac程序呈上-

邻接表+深度优先遍历+spfa

请不要拿以下代码直接AC，仅给参考，代码不完美，因为是新人，这种类型的题目没怎么练还
注：该题完美题解请看上面！
诶~太有强迫症爱换行- -这代码看起来好长越发显得我算法脑残了。。。

block code

program ex;
var data:array[1..10000,1..10000] of longint;
n,m,x,y,s,t,i,k,ans,len,a:longint;
num,spfa,leave:array[1..10000] of longint;
can,can2,have:array[1..10000] of boolean;
ps:boolean;

procedure search(xx:longint); //寻找可以去终点的点，反向搜索，也可以spfa或者BFS寻找
var i:longint;
begin
for i:=1 to leave[xx] do
begin
if can[data[xx,i]]=false then
begin
can[data[xx,i]]:=true;
search(data[xx,i]);
end;
end;
end;

procedure search2; //排除那些类似样例2中2的点，其实可以直接spfa找最短路的时候排除。脑残了
var i,k:longint;
begin
ps:=false;
for i:=1 to n do
if can[i]=false then
for k:=1 to leave[i] do
if can2[data[i,k]]=true then
begin
ps:=true;
can2[data[i,k]]:=false;
break;
end;
end;
procedure spfa1(xx2:longint); //弱弱的spfa，第一次写呢~
var i,k:longint;
begin

for i:=1 to leave[xx2] do
if (can2[data[xx2,i]]=true) and (num[xx2]+1<num[data[xx2,i]]) then
begin
num[data[xx2,i]]:=num[xx2]+1;
if have[data[xx2,i]]=false then
begin
len:=len+1;
spfa[len]:=data[xx2,i];
end;
end;

have[num[xx2]]:=false;

for i:=1 to len do
spfa[i]:=spfa[i+1];

len:=len-1;

end;

begin //main
read(n); read(m);
fillchar(data,sizeof(data),0);
fillchar(can,sizeof(can),false);
fillchar(have,sizeof(have),false);
fillchar(spfa,sizeof(spfa),0);
fillchar(can2,sizeof(can2),false);
fillchar(leave,sizeof(leave),0);
for i:=1 to n do
num[i]:=maxlongint;

ans:=maxlongint;
ps:=true;
len:=1;
for i:=1 to m do
begin
read(x); read(y);
if x<>y then
begin
leave[y]:=leave[y]+1;
data[y,leave[y]]:=x;
end;
end;

read(s); read(t);
spfa[1]:=t; //注意起点终点一些数据的初始化
num[t]:=0;
have[t]:=true;

search(t);
if can[s]=false then
begin
write('-1'); //终点去不了起点，肯定要-1
exit;
end;

can[t]:=true;

for i:=1 to n do
can2[i]:=can[i];

while ps=true do
search2;

while len<>0 do //spfa
begin
spfa1(spfa[1]);
end;

write(num[s]); //ans

end.

把起点和终点连起来，做一遍scc（竞赛学弟的想法，看起来是可以的，如果知道反例，麻烦回复一下。。。）

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>

#define MX 10002

#define INF 0x7fffffff

using namespace std;

short pmap[MX][MX];
short rmap[MX][MX];
short book[MX];
short cantbook[MX];
int pnum[MX];
int rnum[MX];
int n,m,s,t;

int createm(int targ)
{
int q[MX*2];
int head,tail;

int src;

head=tail=0;
memset(book,0,sizeof(book));
q[head]=targ;
book[targ]=1;
while(head>=tail)
{
src=q[tail];
for(int i=1; i<=rnum[src]; i++)
{
if(rmap[src][i]==1&&book[i]==0)
{
head++;
book[i]=1;
q[head]=i;
}
}
tail++;
}

if(book[s]==0)
{
cantbook[s]=1;
return 0;
}

for(int i=1; i<=n; i++)
if(book[i]==0)
{
cantbook[i]=1;
for(int j=1; j<=rnum[i]; j++)
if(rmap[i][j])
cantbook[j]=1;
}
return 0;
}

int work(int from,int to)
{
int q[MX];
int bkp[MX];
int dist[MX];
int head,tail;

int src;

memset(q,0,sizeof(q));
memset(bkp,0,sizeof(bkp));
for(int i=1;i<=n;i++)
dist[i]=INF;

head=tail=1;
q[head]=from;
bkp[from]=1;
dist[from]=0;

while(head>=tail)
{
src=q[tail];
for(int i=1;i<=pnum[src];i++)
{
if(pmap[src][i]==1&&cantbook[i]==0)
{
if(dist[src]+1<dist[i])
{
dist[i]=dist[src]+1;
if(bkp[i]==0)
{
bkp[i]=1;
head++;
q[head]=i;
}
}
}
}
bkp[q[tail]]=0;
tail++;
}
if(dist[to]==INF)
return -1;
else
return dist[to];
return 0;
}

int input()
{
int a,b;
scanf("%d%d",&n,&m);
for(int i=1; i<=m; i++)
{
scanf("%d%d",&a,&b);
pmap[a][b]=1;
pnum[a]=max(pnum[a],b);
rmap[b][a]=1;
rnum[b]=max(rnum[b],a);
}
scanf("%d%d",&s,&t);
return 0;
}

int main()
{
input();
createm(t);
if(cantbook[s]==1)
{
cout<<-1<<endl;
return 0;
}
cout<<work(s,t)<<endl;
return 0;
}