描述

在有向图 G 中，每条边的长度均为 1，现给定起点和终点，请你在图中找一条从起点到 终点的路径，该路径满足以下条件：

1. 路径上的所有点的出边所指向的点都直接或间接与终点连通。
2. 在满足条件 1 的情况下使路径最短。

注意：图 G 中可能存在重边和自环，题目保证终点没有出边。 请你输出符合条件的路径的长度。

格式

输入格式

第一行有两个用一个空格隔开的整数 n 和 m，表示图有 n 个点和 m 条边。

接下来的 m 行每行 2 个整数 x、y，之间用一个空格隔开，表示有一条边从点 x 指向点y。

最后一行有两个用一个空格隔开的整数 s、t，表示起点为 s，终点为 t。

输出格式

输出只有一行，包含一个整数，表示满足题目描述的最短路径的长度。

如果这样的路径不存在，输出-1。

样例1

样例输入1

 

3 21 22 11 3

样例输出1

 

-1

样例2

样例输入2

 

6 61 21 32 62 54 53 41 5

样例输出2

 

3

限制

对于 30%的数据，0 < n ≤ 10，0 < m ≤ 20；

对于 60%的数据，0 < n ≤ 100，0 < m ≤ 2000；

对于 100%的数据，0 < n ≤ 10,000，0 < m ≤ 200,000，0 < x，y，s，t ≤ n，x ≠ t。

提示

【输入输出样例1说明】

如上图所示，箭头表示有向道路，圆点表示城市。起点 1 与终点 3 不连通，所以满足题目描述的路径不存在，故输出-1。

【输入输出样例2说明】

如上图所示，满足条件的路径为 1->3->4->5。注意点 2 不能在答案路径中，因为点 2 连了一条边到点 6，而点 6 不与终点 5 连通。

来源

NOIP2014 提高组 Day2

---

 

 

一开始错解题意了，以为只要是能到那些不连通终点的点的所有点都不能要，就全W了

后来才明白只用找和这些达不到终点的点直接相连的点就可以了，都是语文太差了。。。

方法很简单

就是先反向存图，从终点开始dfs一次把终点不能到的点标记出来

然后把所有和这些点直接相连的点也标记了，最后来一遍bfs

AC代码

1 #include
          
             2 #include
           
              3 #include
            
               4 #include
             
                5 #define MAX 2000005  6 using namespace std;  7 int n,m;  8 int tot;  9 int s,t; 10 int ans; 11 int totz; 12 int v1,v2; 13 struct xx{
        int num,step;}; 14 queue
              
               way; 15 int vis[10005]; 16 int vis2[10005]; 17 int innum[10005]; 18 int cannot[10005]; 19 int outnum[10005];//出度  20 int head[10005],next[MAX],tov[MAX]; 21 int headz[10005],nextz[MAX],tovz[MAX]; 22 void add(int a,int b) 23 { 24     tot++; 25     tov[tot]=b; 26     next[tot]=head[a]; 27     head[a]=tot; 28 } 29 void addz(int a,int b) 30 { 31     totz++; 32     tovz[totz]=b; 33     nextz[totz]=headz[a]; 34     headz[a]=tot; 35 } 36 void dfs(int k) 37 { 38     if(vis[k])return; 39     vis[k]=1; 40     for(int i=head[k];i;i=next[i]) 41         dfs(tov[i]); 42 } 43 void del(int k) 44 { 45     cannot[k]=1; 46     for(int i=head[k];i;i=next[i]) 47     if(!cannot[tov[i]]) 48         cannot[tov[i]]=1; 49 } 50 void BFS() 51 { 52     xx des,v,u; 53     des.num=s; 54     des.step=0; 55     way.push(des); 56     while(!way.empty()) 57     { 58         u=way.front(); 59         way.pop(); 60         for(int i=headz[u.num];i;i=nextz[i]) 61         if(!vis2[tovz[i]]&&!cannot[tovz[i]]) 62         { 63             v.num=tovz[i]; 64             vis2[v.num]=1; 65             v.step=u.step+1; 66             if(v.num==t) 67             { 68                 cout<
               
                >n>>m; 80 for(int i=1;i<=m;i++) 81 { 82 scanf("%d%d",&v1,&v2); 83 if(v2!=v1)//自环 84 { 85 add(v2,v1);//反存边 86 addz(v1,v2); 87 outnum[v1]++; 88 innum[v2]++; 89 } 90 } 91 cin>>s>>t; 92 //if(s==t){cout<<"0";return 0;} 93 //if(outnum[s]==0||innum[t]==0){cout<<"-1";return 0;} 94 dfs(t);//从终点出发扩展一次找出不能直接或间接到终点的点 95 //if(!vis[s]){cout<<"-1";return 0;} 96 for(int i=1;i<=n;i++) 97 if(!vis[i]&&!cannot[i]) 98 del(i); 99 cannot[s]=0;//起点必须可以走 100 BFS();101 cout<<"-1";102 return 0;103 }