先用dfs从终点向前找，看哪些点能到终点。然后再访问每个点，判断它的后继是否能到终点。最后跑一遍sssp。
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <queue>

using namespace std;

#define INF 2000000000
struct Node {
int nextNode, length;
Node *next;
} *N[10001], *P[10001], pool[400005];

int n, m;
int poolcnt;
int s, t;
bool vis[10001], can[10001];

inline int in() {
int RV = 0;
char p = getchar();
while (!isdigit(p)) {
p = getchar();
}
while (isdigit(p)) {
RV *= 10;
RV += (p - '0');
p = getchar();
}
return RV;
}
void addedge(int x, int y, int l) {
Node *p = &pool[++poolcnt];
p->nextNode = y;
p->length = l;
p->next = N[x];
N[x] = p;
p = &pool[++poolcnt];
p->nextNode = x;
p->length = l;
p->next = P[y];
P[y] = p;
}
void dfs(int k) {
vis[k] = true;
for (Node *p = P[k]; p; p = p->next) {
if (!vis[p->nextNode]) {
dfs(p->nextNode);
}
}
}
void check() {
for (int i = 1; i <= n; ++i) {
if (!vis[i])
continue;
can[i] = true;
for (Node *p = N[i]; p; p = p->next) {
if (!vis[p->nextNode]) {
can[i] = false;
break;
}
}
}
}
int dist[10001];
struct Node2 {
int num, val;
bool operator < (const Node2 &xx) const {
return val > xx.val;
}
};
bool vis0[10001];
void sssp(int k) {
priority_queue<Node2> q;
for (int i = 1; i <= n; ++i)
dist[i] = INF;
dist[k] = 0;
q.push((Node2){k, 0});
while (!q.empty()) {
Node2 x = q.top();
q.pop();
if (vis0[x.num] || !can[x.num]) continue;
vis0[x.num] = true;
for (Node *p = N[x.num]; p; p = p->next) {
if (can[p->nextNode] && dist[p->nextNode] > dist[x.num] + p->length) {
dist[p->nextNode] = dist[x.num] + p->length;
q.push((Node2){p->nextNode, dist[p->nextNode]});
}
}
}
}
int main(int argc, const char argv[]) {
scanf("%d %d", &n, &m);
int x, y;
for (int i = 1; i <= m; ++i) {
x = in();
y = in();
addedge(x, y, 1);
}
scanf("%d %d", &s, &t);
dfs(t);
check();/
for (int i = 1; i <= n; ++i) {
printf("<%d %d>\n", i, can[i]);
}*/
sssp(s);
if (dist[t] >= INF) {
printf("-1\n");
}
else {
printf("%d\n", dist[t]);
}
return 0;
}

###FFFFFFFFUUUUUUUUCCCCCCCCKKKKKKKK
评测状态 Time Limit Exceeded
题目 P1909 寻找道路
递交时间 2015-11-06 16:10:00
代码语言 C++
评测机 VijosEx
消耗时间 1379 ms
消耗内存 4048 KiB
评测时间 2015-11-06 16:10:03
评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 3820 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 3824 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 3820 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 3824 KiB, score = 10
测试数据 #4: Accepted, time = 2 ms, mem = 3820 KiB, score = 10
测试数据 #5: Accepted, time = 4 ms, mem = 3820 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 3836 KiB, score = 10
测试数据 #7: Accepted, time = 312 ms, mem = 3916 KiB, score = 10
测试数据 #8: Accepted, time = 31 ms, mem = 3900 KiB, score = 10
测试数据 #9: TimeLimitExceeded, time = 1015 ms, mem = 4048 KiB, score = 0
TimeLimitExceeded, time = 1379 ms, mem = 4048 KiB, score = 90
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int s,t,cnt,bcnt,nxt[200010],fir[10010],to[200010],
bnxt[200010],bfir[10010],bto[200010],dotot[10010],dot[10010];
bool dl[10010];
void add(int a,int b)
{
nxt[++cnt]=fir[a];
fir[a]=cnt;
to[cnt]=b;
}
void badd(int a,int b)
{
bnxt[++bcnt]=bfir[a];
bfir[a]=bcnt;
bto[bcnt]=b;
}
void psearch(int node)
{
dot[node]++;
if(dot[node]<2)
for(int i=bfir[node];i;i=bnxt[i])
psearch(bto[i]);
}
void search(int node)
{
for(int i=fir[node];i;i=nxt[i])
{ if(dl[to[i]])continue;
if(dot[to[i]]==-1||dot[node]+1<dot[to[i]]){
dot[to[i]]=dot[node]+1;
search(to[i]);
}
}
}
int main()
{
//freopen("","r",stdin);
//freopen("","w",stdout);
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
dotot[a]++;
badd(b,a);
}
scanf("%d%d",&s,&t);
psearch(t);
for(int i=1;i<=n;i++)
{
if(i==t)continue;
if(dotot[i]!=dot[i])dl[i]=true;
}
memset(dot,-1,sizeof(dot));dot[s]=0;
if(!dl[s])search(s);
else {
printf("-1\n");
return 0;
}
printf("%d\n",dot[t]);
return 0;
}

评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 960 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 956 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 960 KiB, score = 10

测试数据 #3: Accepted, time = 0 ms, mem = 956 KiB, score = 10

测试数据 #4: Accepted, time = 0 ms, mem = 956 KiB, score = 10

测试数据 #5: Accepted, time = 0 ms, mem = 960 KiB, score = 10

测试数据 #6: Accepted, time = 0 ms, mem = 1100 KiB, score = 10

测试数据 #7: Accepted, time = 15 ms, mem = 1716 KiB, score = 10

测试数据 #8: Accepted, time = 0 ms, mem = 1140 KiB, score = 10

测试数据 #9: Accepted, time = 62 ms, mem = 4104 KiB, score = 10

Accepted, time = 77 ms, mem = 4104 KiB, score = 100

代码
program P1909;

type
point=^link;
link=record
data:longint;
next:point;
end;
var
e:array[1..10000] of point;
n,m:longint;
star,t:longint;
x,y:longint;
flag:array[1..10000] of boolean;
can:array[1..10000] of boolean;
i,j:longint;

procedure init;
var
i:longint;
begin
fillchar(flag,sizeof(flag),false);
fillchar(can,sizeof(can),true);
for i:=1 to n do
e[i]:=nil;
end;

procedure inser(x,y:longint);
var
p:point;
begin
new(p);
p^.data:=x;
p^.next:=e[y];
e[y]:=p;
end;

procedure bfs1;
var
tmp:point;
d:longint;
head,tail:longint;
fifo:array[1..10000] of longint;
visit:array[1..10000] of boolean;
begin
fillchar(visit,sizeof(visit),false);
fifo[1]:=t; flag[t]:=true; visit[t]:=false;
head:=1; tail:=1;
repeat
tmp:=e[fifo[head]];
while tmp<>nil do
begin
d:=tmp^.data;
if visit[d]=false then
begin
flag[d]:=true;
visit[d]:=true;
inc(tail);
fifo[tail]:=d;
end;
tmp:=tmp^.next;
end;
inc(head);
until head>tail;
end;

procedure clean;
var
tmp:point;
d:longint;
i:longint;
begin
for i:=1 to n do
begin
if flag[i]=false then
begin
tmp:=e[i];
while tmp<>nil do
begin
d:=tmp^.data;
can[d]:=false;
tmp:=tmp^.next;
end;
end;
end;
end;

procedure bfs2;
var
tmp:point;
d:longint;
head,tail:longint;
fifo:array[1..10000] of longint;
step:array[1..10000] of longint;
visit:array[1..10000] of boolean;
s:longint;
begin
fillchar(visit,sizeof(visit),false);
fillchar(step,sizeof(step),0);
fifo[1]:=t; visit[t]:=true;
head:=1; tail:=1; s:=0;
repeat
tmp:=e[fifo[head]]; s:=step[fifo[head]];
while tmp<>nil do
begin
d:=tmp^.data;
if (d=star) and (can[d]=true) then
begin
writeln(s+1);
halt;
end;
if (can[d]=true) and (visit[d]=false) then
begin
step[d]:=s+1;
visit[d]:=true;
inc(tail);
fifo[tail]:=d;
end;
tmp:=tmp^.next;
end;
inc(head);
until head>tail;
writeln(-1);
halt;
end;

begin
readln(n,m);
init;
for i:=1 to m do
begin
readln(x,y);
inser(x,y);
end;
readln(star,t);
bfs1;
clean;
if can[star]=false then
begin
writeln(-1);
halt;
end;
bfs2;
end.

解题思路大体是反向dfs一遍找出所有不可行点，再bfs一遍求最短路
对于bfs来说无所谓方向，不妨也反向，就不用存正向邻接表了
用vector代替了所有内置数组，再借助读入优化，使得总耗时139 ms，总内存2832 KiB
为了使代码短小精**（zhuang）**悍**（bi）**，代码格式可能有点古怪
递交时间 2015-10-31 17:32:29
代码语言 C++
评测机 VijosEx
消耗时间 139 ms
消耗内存 2832 KiB
评测时间 2015-10-31 17:32:32
测试数据 #0: Accepted, time = 0 ms, mem = 532 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 532 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 532 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 536 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 540 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 548 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 680 KiB, score = 10
测试数据 #7: Accepted, time = 31 ms, mem = 1240 KiB, score = 10
测试数据 #8: Accepted, time = 15 ms, mem = 1312 KiB, score = 10
测试数据 #9: Accepted, time = 78 ms, mem = 2832 KiB, score = 10
Accepted, time = 139 ms, mem = 2832 KiB, score = 100
#include<cstdio>
#include<vector>
#include<deque>
using namespace std;
int n,s,t;
vector<vector<int> > rw;//反向邻接表
vector<bool> visited,cango;
//分别是DfsBfs的共用标记数组，及标记是否可出现在所求路径上的点
int getint()//读入优化
{
int ans=0;
for(char ch=getchar(); ch>='0'&&ch<='9'; ch=getchar())
ans=ans*10+ch-'0';
return ans;
}
void dfs(const int &k)
{
visited[k]=1;
for(vector<int>::iterator
i=rw[k].begin(); i!=rw[k].end(); ++i)
if(!visited[*i])dfs(*i);
}
int bfs()
{
vector<int> dist(n,-1);
dist[t]=0;
visited.assign(n,0);
visited[t]=1;
for(deque<int> que(1,t); !que.empty(); que.pop_front())
for(vector<int>::iterator i=rw[que.front()].begin();
i!=rw[que.front()].end(); ++i)
if(cango[*i]&&!visited[*i])
{
dist[*i]=dist[que.front()]+1;
if(*i==s)return dist[s];
que.push_back(*i);
visited[*i]=1;
}
return dist[s];
}
int main()
{
n=getint();
rw.assign(n,vector<int>());//利用成员函数assign初始化
for(int m=getint(); m--; rw[t].push_back(s))
{
s=getint()-1;
t=getint()-1;
}
//判断每个点是否可出现在最短路径上
visited.assign(n,0);
cango.assign(n,1);
s=getint()-1;
dfs(t=getint()-1);
for(int k=0; k!=n; ++k)
if(!visited[k])
{
cango[k]=0;
for(vector<int>::iterator
i=rw[k].begin(); i!=rw[k].end(); ++i)
cango[*i]=0;
}
printf("%d",bfs());
}

受不了了，输入函数自己写的，数组全开成了char型，最后一个点就是超时，哪位大神帮帮我，多多感谢了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define begin s
#define end q
using namespace std;
int n,m,x,y,begin,end,dis[10001];
char f[10001][10001];
bool b[10001],c[10001],have[10001];
void read(int&t)
{
char x;
t=0;
while(1){
x=getchar();
if(x>='0'&&x<='9'){
t=t*10+(x-'0');
}
else{
break;
}
}
}
void init()
{
int i;
memset(b,false,sizeof(b));
memset(c,false,sizeof(c));
memset(dis,127/3,sizeof(dis));
memset(have,false,sizeof(have));
read(n);
read(m);
for(i=1;i<=m;i++){
read(x);
read(y);
f[x][y]='1';
}
scanf("%d%d",&begin,&end);
b[end]=true;
c[end]=true;
}
void change1(int t)
{
int i;
for(i=1;i<=n;i++){
if(f[i][t]=='1' and !c[i]){
b[i]=true;
c[i]=true;
change1(i);
}
}
return;
}
void change2()
{
int i,j;
for(i=1;i<=n;i++){
if(!c[i]){
b[i]=false;
for(j=1;j<=n;j++){
if(f[j][i]=='1'){
b[j]=false;
}
}
}
}
}
void dijkstra()
{
int i;
dis[begin]=0;
while(1){
int k=0;
for(i=1;i<=n;i++){
if(dis[i]<dis[k]&&!have[i]){
k=i;
}
}
if(k==0){
break;
}
have[k]=true;
for(i=1;i<=n;i++){
if(dis[k]+(f[k][i]-'0')<dis[i] and b[i] and f[k][i]=='1'){
dis[i]=dis[k]+(f[k][i]-'0');
}
}
if(dis[end]!=dis[0]){
break;
}
}
if(dis[end]==dis[0]){
printf("-1");
}
else{
printf("%d",dis[end]);
}
}
int main()
{
init();
change1(end);
change2();
dijkstra();
return 0;
}

时隔一年。看楼底下自己第一个发的题解。笑的不行

每个点300MS，总时间2000MS，开了10000x10000的数组，390000的数据

如今总时间92MS，4000数据水过此题。

向各位分享下蒟蒻2次代码的区别

楼底下的那份。通过邻接表存反图（正图不存（原因在下面自己慢慢看），意思就是边全部反向）然后DFS搜索所有不符合要求的点，再DFS一次把路径上不符合的点排除干净。最后spfa（而且是不标准的SPFA= =），因此只需要判断一次-1情况即可（看我楼底下代码），即can2中true的点必定可以从终点走到。

这次我的代码，存图用了前向星存反图，大大减少空间，然后2遍spfa秒杀。**其实看楼下这些存2张图的哥们。最短路从起点和从终点走起点不一样么？存2张图累不累= =，没必要正反spfa什么的啊！**
然后先走一遍spfa。所有无法扩展到的点can数组中记录为false，然后根据can数组把每个false的点的出度也全部改为false、

但是和我一年前代码不同的是。我不能确定能否从终点到达can2标记为true的点。也就是说一年前我的算法是不断扩展走不到的点。而这次我只是把不能走的点的出度给标记了，这样省时间。

因此当我们再spfa一次的时候可能起点无法被扩展（我是从终点往回走的），因为可能必要道路上某个点不符合条件了。

简单的说，SPFA一次，不能走到的点就是不符合的点，所有不符合的点的出度也不符合，然后重新走spfa，如果起点还是无限大，就是没答案，如果有答案就输出。就这样

因此还要再判断一次-1.其实完全不用想太多一样的，

下面给出我的代码
###pascal code
program P1909;
var a,map:array[1..200000,1..2] of longint;
s,first,last,dis:array[1..10001] of longint;
team:array[1..20009] of longint;
can,have,can2:array[1..10000] of boolean;
i,j,m,n,head,tail,s2,t,len:longint;
procedure search; //出度标记为false
var i,j:longint;
begin
for i:=1 to n do
if can[i]=false then
for j:=first[i] to last[i] do
can2[map[j,2]]:=false;
end;

procedure next(var x:longint); //SPFA的循环队列优化
begin
inc(x); if x>20009 then dec(x,20009);
end;

procedure spfa; //SPFA不用说了吧？
var i,j,now:longint;
begin
while head<=tail do
begin
now:=team[head];
for i:=first[now] to last[now] do
if (dis[now]+1<dis[map[i,2]]) and (can2[map[i,2]]=true) then
begin
dis[map[i,2]]:=dis[now]+1;
if have[map[i,2]]=false then
begin
next(tail); team[tail]:=map[i,2]; have[map[i,2]]:=true;
end;
end;
have[now]:=false; next(head);
end;
end;

procedure star; //计数排序的前向星
var i,j,x,num1,num2,len:longint;
begin
len:=0;
for i:=1 to m do
begin
read(num1,num2);
if num1<>num2 then
begin
inc(len); a[len,2]:=num1; a[len,1]:=num2; inc(s[a[len,1]]);
end;
end;
first[1]:=1;
for i:=2 to n do begin first[i]:=first[i-1]+s[i-1]; last[i]:=first[i]-1; end;
for i:=1 to len do
begin
inc(last[a[i,1]]); x:=last[a[i,1]]; map[x,1]:=a[i,1]; map[x,2]:=a[i,2];
end;
end;

begin
read(n,m);
fillchar(s,sizeof(s),0); fillchar(first,sizeof(first),0);
fillchar(last,sizeof(last),0); fillchar(team,sizeof(team),0);
fillchar(can,sizeof(can),true); fillchar(dis,sizeof(dis),\(7f div 3);
fillchar(have,sizeof(have),false); fillchar(can2,sizeof(can2),true);
star; read(s2,t); head:=1; tail:=1; team[1]:=t; have[t]:=true; dis[t]:=0;
spfa;
for i:=1 to n do
if dis[i]=dis[10001] then
begin
can[i]:=false; can2[i]:=false;
end;
if can2[s2]=false then begin write('-1'); exit; end;
search;
if can2[s2]=false then begin write('-1'); exit; end;
fillchar(dis,sizeof(dis),\)7f div 3); fillchar(team,sizeof(team),0);
head:=1; tail:=1; team[1]:=t; have[t]:=true; dis[t]:=0;
spfa;
if dis[s2]=dis[10001] then begin write('-1'); exit; end;
write(dis[s2]);
end.

//一张正图一张反图，先反着dfs，正面用了下dijkstra


#include <cstdio>
#include <cctype>
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 10000 + 5;
const int MAXM = 200000 + 5;
const int INF = 0x7f7f7f7f;
int first1[MAXN], first2[MAXN];
long long dis[MAXN];
bool vis1[MAXN], vis2[MAXN];
int s, t, n, m, cnt1 = 1, cnt2 = 1;
struct E {
    int u, to, next;
} e1[MAXM], e2[MAXM];//前向星，存了两张图
//存图也写成了两个，可以简化；
inline void add1(int u, int v) {
    e1[++cnt1].to = v;
    e1[cnt1].next = first1[u];
    first1[u] = cnt1;
}

inline void add2(int u, int v) {
    e2[++cnt2].to = v;
    e2[cnt2].next = first2[u];
    first2[u] = cnt2;
}

void dfs(int u) {
    if (vis2[u])return;
    vis2[u] = true;
    for (int e = first2[u]; e; e = e2[e].next) {
        int x = e2[e].to;

        dfs(x);
    }
}

int in();

int main() {
    n = in(), m = in();
    memset(vis1, 0, sizeof(vis1));
    memset(vis2, 0, sizeof(vis2));
    memset(dis, 0x7f, sizeof(dis));
    memset(first1, 0, sizeof(first1));
    memset(first2, 0, sizeof(first2));
    for (int i = 1; i <= m; ++i) {
        int x, y;
        x = in(), y = in();
        add1(x, y);
        add2(y, x);
    }
    s = in(), t = in();


    dfs(t);

    for (int x = 1; x <= n; ++x) {
        if (!vis2[x]) {
            vis1[x] = true;
            for (int e = first2[x]; e; e = e2[e].next) {
                int y = e2[e].to;
                vis1[y] = true;
                //cout<<y<<" pointed."<<endl;
            }

        }
    }

    dis[s] = 0;
    //dijkstra
    for (int i = 1; i <= n; ++i)//just loop n times
    {
        int minn = INF;
        int x = -1;


        for (int j = 1; j <= n; ++j) {
            if (!vis1[j] && dis[j] <= minn) {
                minn = dis[j];
                x = j;
            }
        }
        vis1[x] = true;
        if (x != -1) {
            for (int e = first1[x]; e; e = e1[e].next) {
                int y = e1[e].to;
                dis[y] = min(dis[y], dis[x] + 1LL);
            }

        } else continue;
    }


    if (dis[t] >= 0x7f7f7f7f7f7f7f7fLL)printf("-1\n");
    else printf("%I64d\n", dis[t]);
    return 0;
}


int in() {
    int c = getchar(), ans = 0;
    while (!isdigit(c))c = getchar();
    while (isdigit(c)) {
        ans *= 10;
        ans += c - '0';
        c = getchar();
    }
    return ans;
}

    

http://www.cnblogs.com/JSZX11556/p/4907703.html

我去...把所有cin改称scanf，最后一组数据直接从1016ms降到234ms...醉得不行啊

cin害人不浅！！！
节省了一半时间！！！

#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<map>
using namespace std;
queue<int>q,yu[10000],hua[10000];
int m,n;
int x,y;
set<int>ku;
map<int,int>hu;
int flag[10000]={1};
int father[10000]={1};
int w[10000][10000];
void yuxiating(int qq,int w)
{if(w==qq)return ;
while(!hua[w].empty())
{
int oo=hua[w].front();
hua[w].pop();
ku.erase(oo);
yuxiating(qq,oo);

}
}
int sum;
int pan(int qq,int w)
{ q.push(qq);
hu[qq]=0;
while(!q.empty())
{

int oo=q.front();
q.pop();
sum=hu[oo];

while(!yu[oo].empty())
{
int ooo=yu[oo].front();
yu[oo].pop();

if(flag[ooo]==0)
{

if(ooo==w){return sum+1;}

if(father[ooo]==0){
q.push(ooo);hu[ooo]=sum+1;father[ooo]=1;}

}
}
}
return -1;
}
int main ()
{
memset(flag,0,sizeof(flag));
memset(father,0,sizeof(father));
scanf("%d%d",&m,&n);
for(int i=1;i<=n;i++)
{ku.insert(i);
int a,b;
scanf("%d%d",&a,&b);
w[b][a]=1;
yu[a].push(b);
hua[b].push(a);
}
scanf("%d%d",&x,&y);
yuxiating(x,y);
ku.erase(y);
for(set<int>::iterator it=ku.begin();it!=ku.end();it++)
{
for(int i=1;i<=n;i++){if(w[*it][i]){flag[i]=1;}}

}
flag[y]=0;
cout<<pan(x,y);
return 0;
}

2次bfs加个简单的处理即可

先求反图，从终点遍历，之后标记无法过的点，最后SPFA，我的代码有点长，但思路清晰
program road(input,output);
var a,b,a1,b1,d:array[-11..200000] of longint;
head,tail,i,j,n,m,x,y,e,now,ss,tt:longint;
first1,last1,first2,last2,dist:array[-11..10000] of longint;
flag,flag1,canto:array[-11..10000] of boolean;
procedure qsort_yuantu(l,r:longint);
var i,j,key,t:longint;
begin
i:=l;
j:=r;
key:=a[(i+j) div 2];
repeat
while a[i]<key do inc(i);
while a[j]>key do dec(j);
if i<=j then
begin
t:=a[i];a[i]:=a[j];a[j]:=t;
t:=b[i];b[i]:=b[j];b[j]:=t;
inc(i);dec(j);
end;
until i>j;
if i<r then qsort_yuantu(i,r);
if l<j then qsort_yuantu(l,j);
end;
procedure qsort_fantu(l,r:longint);
var i,j,key,t:longint;
begin
i:=l;
j:=r;
key:=a1[(i+j) div 2];
repeat
while a1[i]<key do inc(i);
while a1[j]>key do dec(j);
if i<=j then
begin
t:=a1[i];a1[i]:=a1[j];a1[j]:=t;
t:=b1[i];b1[i]:=b1[j];b1[j]:=t;
inc(i);dec(j);
end;
until i>j;
if i<r then qsort_fantu(i,r);
if l<j then qsort_fantu(l,j);
end;
procedure bfs_fantu(n:longint);
var d:array[-1..50000] of longint;
head,tail,now:longint;
begin
flag1[n]:=true;head:=1;tail:=1;d[head]:=n;
while head<=tail do
begin
now:=d[head];
if (first2[now]<>0) and (last2[now]<>0) then
for i:=first2[now] to last2[now] do
begin
if flag1[b1[i]]=false then
begin
flag1[b1[i]]:=true;
inc(tail);
d[tail]:=b1[i];
end;
end;
inc(head);
end;
end;
procedure spfa(start:longint);
var d:array[-1..200000] of longint;
head,tail,now:longint;
begin
for i:=1 to n do flag[i]:=false;
head:=1;tail:=1;d[head]:=start;flag[start]:=true;
dist[start]:=0;
while head<= tail do
begin
now:=d[head];
if (first1[now]<>0) and (last1[now]<>0) then
for i:=first1[now] to last1[now] do
if (dist[b[i]]>=dist[now]+1)and(canto[b[i]]) then
begin
dist[b[i]]:=dist[now]+1;
if flag[b[i]]=false then
begin
flag[b[i]]:=true;
inc(tail);
d[tail]:=b[i];
end;
end;
flag[now]:=false;
inc(head);
end;

end;
begin
fillchar(a,sizeof(a),0);
fillchar(b,sizeof(b),0);
fillchar(a1,sizeof(a1),0);
fillchar(b1,sizeof(b1),0);
fillchar(first1,sizeof(first1),0);
fillchar(first2,sizeof(first2),0);
fillchar(last1,sizeof(last1),0);
fillchar(last2,sizeof(last2),0);
fillchar(flag,sizeof(flag),false);
fillchar(flag1,sizeof(flag1),false);
fillchar(canto,sizeof(canto),false);
readln(n,m);
for i:=1 to m do
begin
readln(x,y);
inc(e);
a[e]:=x;b[e]:=y;
a1[e]:=y;b1[e]:=x;
end;
qsort_fantu(1,e);
now:=a1[1];
first2[a1[1]]:=1;
for i:=2 to e do
begin
if now<>a1[i] then
begin
last2[now]:=i-1;
now:=a1[i];
first2[now]:=i;
end;
end;
last2[now]:=e;
qsort_yuantu(1,e);
now:=a[1];
first1[a[1]]:=1;
for i:=2 to e do
begin
if now<>a[i] then
begin
last1[now]:=i-1;
now:=a[i];
first1[now]:=i;
end;
end;
last1[now]:=e;
readln(ss,tt);//读入起点ss和终点tt
bfs_fantu(tt);
for i:=1 to n do canto[i]:=flag1[i];
for i:=1 to n do
if flag1[i]=false then
for j:=first2[i] to last2[i] do
begin
canto[b1[j]]:=false;
end;
for i:=1 to n do dist[i]:=maxlongint shr 1;
//spfa(ss);
now:=ss;head:=1;tail:=1;d[head]:=ss;flag[ss]:=true;dist[ss]:=0;
while head<=tail do
begin
now:=d[head];
for i:=first1[now] to last1[now] do
begin
if (dist[b[i]]>=dist[now]+1)and(canto[b[i]]) then
begin
dist[b[i]]:=dist[now]+1;
if flag[b[i]]=false then
begin
flag[b[i]]:=true;
inc(tail);
d[tail]:=b[i];
end;
end;
end;
flag[now]:=false;
inc(head);
end;
// for i:=1 to tail do writeln(d[i],'//');
// for i:=1 to n do writeln(i,' ',canto[i]);
// for i:=first1[3] to last1[3]do writeln(a[i],' ',b[i],'##');
if dist[tt]<>maxlongint shr 1 then writeln(dist[tt])
else writeln(-1);
end.

1.读入的时候同时存正图和反图
2.从终点dfs反图一遍，标记终点不能到达的点
3.遍历反图中终点不能到达的点的出边，在正图中把那些边指向点clear掉
4.此时正图处理完毕了，bfs求最短路即可

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
#define inf 10000000
using namespace std;
vector <int>to1[10100],cost1[10100],to2[10100],cost2[10100];
//to1,cost1 正图。to2,cost2 反图
int n,m,s,t;
int ds[10100];
bool can[10100],vis[10100];
inline void SPFA1()
{
int S=s;
static queue <int> q;
memset(vis,false,sizeof(vis));
fill(ds,ds+10100,inf);
ds[S]=0; vis[S]=1; q.push(S);
while(!q.empty()){
int x=q.front(); q.pop(); vis[x]=0;
for(int i=0;i<to1[x].size();i++){
int y=to1[x][i],c=cost1[x][i];
if(ds[y]>ds[x]+c&&can[y]){
ds[y]=ds[x]+c;
if(!vis[y]){
vis[y]=1; q.push(y);
}
}
}
}
}
inline void SPFA2()
{
int S=t;
static queue <int> q;
fill(ds,ds+10100,inf);
ds[S]=0; vis[S]=1; q.push(S);
while(!q.empty()){
int x=q.front(); q.pop(); vis[x]=0;
for(int i=0;i<to2[x].size();i++){
int y=to2[x][i],c=cost2[x][i];
if(ds[y]>ds[x]+c){
ds[y]=ds[x]+c;
if(!vis[y]){
vis[y]=1; q.push(y);
}
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
to1[x].push_back(y);cost1[x].push_back(1);
to2[y].push_back(x);cost2[y].push_back(1);
}
scanf("%d%d",&s,&t);
SPFA2();
memset(can,true,sizeof(can));
for(int i=1;i<=n;i++){
if(ds[i]==inf)
for(int j=0;j<to2[i].size();j++)
can[to2[i][j]]=false;
}
SPFA1();
if(ds[t]==inf)
printf("-1");
else
printf("%d",ds[t]);
}

program sss;
type
re=^rrr;
rrr=record
date,ends:longint;
next:re;
end;
var
i,j,k,l,n,m,ii,jj,kk,ll,s,t:longint;
pa,pp:array[0..200000]of re;
dis:array[0..200000]of longint;
dui:array[0..2000000]of longint;
b:array[0..200000]of boolean;

procedure ff(x,y:longint);
var
p:re;
begin
p:=pa[x];
new(pa[x]);
pa[x]^.date:=1;
pa[x]^.ends:=y;
pa[x]^.next:=p;
end;
procedure fff(x,y:longint);
var
p:re;
begin
p:=pp[x];
new(pp[x]);
pp[x]^.date:=1;
pp[x]^.ends:=y;
pp[x]^.next:=p;
end;
function ddd(x:longint):boolean;
var
i,j,k:longint; u:re;
begin
u:=pa[x];
while u<>nil do
begin
if b[u^.ends]=true then
u:=u^.next
else
exit(false);
end;
exit(true);
end;

procedure spfa1(x:longint);
var
p:re; r,l,ii:longint;
begin
fillchar(dis,sizeof(dis),$7f div 3);
dis[x]:=0; l:=0; r:=1; dui[r]:=x;
while l<=r do
begin
inc(l);
ii:=dui[l];
p:=pa[ii];
while p<>nil do
begin
if (dis[p^.ends]>dis[ii]+p^.date)and(ddd(p^.ends)=true) then
begin
dis[p^.ends]:=dis[ii]+p^.date;
inc(r);
dui[r]:=p^.ends;
end;
p:=p^.next;
end;
end;
end;
procedure spfa2(x:longint);
var
p:re; i,j,r,l,ii:longint;
begin
b[x]:=true;
l:=0; r:=1; dui[r]:=x;
while l<=r do
begin
inc(l);
ii:=dui[l];
p:=pp[ii];
while p<>nil do
begin
if b[p^.ends]=false then
begin
b[p^.ends]:=true;
inc(r);
dui[r]:=p^.ends;
end;
p:=p^.next;
end;
end;
end;
begin
readln(n,m);
for i:=1 to m do
begin
readln(ii,jj);
ff(ii,jj);
fff(jj,ii);
end;
readln(s,t);
fillchar(b,sizeof(b),false);
spfa2(t);
spfa1(s);
if dis[t]<10000000 then writeln(dis[t]) else writeln(-1);
end.

蒟蒻去年这道题0分。。。现在刚学图论，反向一次dfs，正向一次bfs过了

#include<stdio.h>

struct way
{
int num,next;
}
;

struct BFS
{
int num,depth;
}
;

struct BFS road[200001];

struct way link1[200001];
struct way link2[200001]; //使用静态邻接表，构造一正一反两个图

int head1[10001]={0};
int head2[10001]={0}; //head是两个图的头指针数组

int bools1[200001]={0};
int bools2[200001]={0}; //bools用于筛选不能经过的点

int oldway[200001]={0}; //oldway用于搜索路径时的判重

void find(int k)
{
int r;
bools2[k]=1;
r=head2[k];
while(r!=0)
{
if(bools2[link2[r].num]==0)
{
bools2[link2[r].num]=1;
find(link2[r].num);
}
r=link2[r].next;
}
}

int main( )
{

int i,j;
int n,m;
int s,t;
int x1,x2;
int len1=0,len2=0;
int p,sum=0;
int head=0,tail=1;

scanf("%d %d",&n,&m);

for(i=1;i<=m;i++)
{
scanf("%d %d",&x1,&x2);

len1++;
link1[len1].num=x2;
link1[len1].next=head1[x1];
head1[x1]=len1;

len2++;
link2[len2].num=x1;
link2[len2].next=head2[x2];
head2[x2]=len2;
}

scanf("%d %d",&s,&t);

p=head2[t];

while(p!=0)
{
if(bools2[link2[p].num]==0)
find(link2[p].num);

p=link2[p].next;
}

bools2[t]=1;

for(i=1;i<=n;i++)
{
if(bools2[i]==0)
{
bools1[i]=1;sum++;
p=head2[i];
while(p!=0)
{
if(bools1[link2[p].num]==0) {bools1[link2[p].num]=1;sum++;}
p=link2[p].next;
}
}
}
//通过对反图的操作，去除所有不能经过的点（bools1数组对应的值为1则不能经过）

road[1].num=s;
road[1].depth=0;
oldway[s]=1;

if (sum==n) printf("-1");
else
{

do
{

head++;

p=head1[road[head].num];

while(p!=0)
{

if(bools1[link1[p].num]==0 && oldway[link1[p].num]==0)
{
tail++;
road[tail].num=link1[p].num;
road[tail].depth=road[head].depth+1;
oldway[road[tail].num]=1;
if(road[tail].num==t) {printf("%d",road[tail].depth);goto endl;}
}

p=link1[p].next;
}

}
while(head<tail);
}

endl:;

return 0;
}

擦 这道题就是一滩水
noip2014时本人把“1.路径上的所有点的出边所指向的点都直接或间接与终点连通”
理解成了“1.路径上的所有点的出边所直接或间接连通的点都直接或间接与终点连通”结果得了10分
语文没学好（话说本人语文扣得分比数英理化生加起来还多）话说要好好学语文
有下面那么麻烦吗 spfa 30行搞定
var
n,m,x,y,s,t,l,r,i,j,he,ti:longint;
a:array[1..10000,0..3000]of longint;
c,d:array[1..100000]of longint;
g:array[1..10000]of boolean;
begin
read(n,m);//输入
for i:=1 to m do begin read(x,y);
inc(a[y,0]);a[y,a[y,0]]:=x;
end;read(l,r);//输入
fillchar(g,sizeof(g),true);
c[1]:=r;for i:=1 to n do d[i]:=1000000000;d[r]:=0;//spfa
he:=0;ti:=1;
while he<ti do begin inc(he);
for i:=1 to a[c[he],0] do
if d[c[he]]+1<=d[a[c[he],i]] then
begin inc(ti);c[ti]:=a[c[he],i];d[a[c[he],i]]:=d[c[he]]+1;end;
end;//spfa
for i:=1 to n do
if d[i]>=1000000000 then begin g[i]:=false;
for j:=1 to a[i,0] do g[a[i,j]]:=false;end;
g[l]:=true;
c[1]:=r;for i:=1 to n do d[i]:=1000000000;d[r]:=0;//spfa
he:=0;ti:=1;
while he<ti do begin inc(he);
for i:=1 to a[c[he],0] do
if (d[c[he]]+1<=d[a[c[he],i]])and g[a[c[he],i]] then

begin inc(ti);c[ti]:=a[c[he],i];d[a[c[he],i]]:=d[c[he]]+1;end;
end;//spfa
if d[l]=1000000000 then writeln(-1)else writeln(d[l]);
end.
122毫秒

【分析】
除了存本题给出的图外，还要存个逆图，用邻接表存储；
排除不连通的点，就用逆图从t点DFS一次，用used[N]存储连不连通，求出所有的used；
设置数组cant[N]，标记每个点能不能取，不能取有两种情况：一是不连通的；二是出边到达不连通的点的点，所以再标记不连通的点的逆图的出边所到达的点；
然后，所有cant[i]=0的点就是可以用的了，再BFS一次求最短路就AC了。
【代码】
#include <cstdio>
#include <cstring>
#include <cstdlib>

using namespace std;

const int N=10001;
const int M=200001;

int n,m,s,t;
struct G
{
int v,next;
}map[M],map1[M];
int tot1,tot,hd1[N],hd[N];
int q[N],l,r=1,level[N];
int used[N],cant[N];

void ins(int u,int v)
{
map[++tot].v=v;
map[tot].next=hd[u];
hd[u]=tot;
}

void ins1(int u,int v)
{
map1[++tot1].v=v;
map1[tot1].next=hd1[u];
hd1[u]=tot1;
}

void init(void)
{
scanf("%d%d",&n,&m);
int x,y;
for (;m--;)
{
scanf("%d%d",&x,&y);
ins(x,y);
ins1(y,x);
}
scanf("%d%d",&s,&t);
}

void DFS(int u)
{
used[u]++;
for (int k=hd1[u];k;k=map1[k].next) if (!used[map1[k].v]) DFS(map1[k].v);
}

void work(void)
{
DFS(t);
for (int i=1;i<=n;i++)
if (!used[i])
{
cant[i]=1;
for (int k=hd1[i];k;k=map1[k].next) cant[map1[k].v]=1;
}
if (cant[s]) {printf("-1\n");return;}
level[q[r]=s]=1;
for (;l^r;)
{
int p=q[++l];
for (int k=hd[p];k;k=map[k].next)
if (!level[map[k].v]&&!cant[map[k].v])
{
if (map[k].v==t) {printf("%d\n",level[p]);return;}
level[map[k].v]=level[p]+1;
q[++r]=map[k].v;
}
}
printf("-1\n");
}

int main(void)
{
init();
work();
return 0;
}
http://shadowchaser.lofter.com/post/1d04e306_5e1d9eb

var d:array[1..10000,1..10000] of boolean;
c:array[1..10000] of integer;
p,dd:array[1..10000] of boolean;

n,m,s,t:longint;
i,j,x,y,k,l,nn:longint;
ans:longint;
begin
fillchar(d,sizeof(d),false);
fillchar(p,sizeof(p),true);
ans:=1;
read(n,m); nn:=n;
for i:=1 to m do
begin
read(x,y);
d[x,y]:=true;
inc(c[x]);
end;
read(s,t);

for i:=1 to n do
if (c[i]=0)and(i<>t) then
begin
p[i]:=false;
for j:=1 to n do
if d[j,i] then begin dec(nn);
p[j]:=false; end;
dec(nn);
end;
i:=1;
if d[s,t] then begin writeln(1); halt; end;
p[s]:=false;
while i<=nn-2 do
begin
fillchar(dd,sizeof(dd),false);
for j:=1 to n do

begin

if d[s,j] and p[j] then

begin
p[j]:=false;

for k:=1 to n do

if (d[j,k]) and(p[k]) then
begin
dd[k]:=true;
end;
inc(i);
end;

end;
inc(ans);
if d[s,t] then begin writeln(ans); halt; end;
d[s]:=dd;
end;
if d[s,t] then writeln(ans)
else writeln(-1);
end.