Noip 2014 senior Day2 寻找道路（road）

【问题描述】

在有向图 G 中，每条边的长度均为 1，现给定起点和终点，请你在图中找一条从起点到

终点的路径，该路径满足以下条件：

1．路径上的所有点的出边所指向的点都直接或间接与终点连通。

2．在满足条件 1 的情况下使路径最短。

注意：图 G 中可能存在重边和自环，题目保证终点没有出边。

请你输出符合条件的路径的长度。

【输入】

输入文件名为 road.in。

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

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

y。

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

【输出】

输出文件名为 road.out。

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

径不存在，输出-1。

【输入输出样例 1】

road.in road.out

3 2 -1

1 2

2 1

1 3

【输入输出样例 2】

6 6 3

1 2

1 3

2 6

2 5

4 5

3 4

1 5

这道题的思路还是蛮好想的，我们找最短路径嘛，用什么SPFA啊，都好。我这里呢是选择建两个图(正向和反向)，先使用DFS跑一遍反向图，将所能到达的点都标记一下，然后我们BFS从S到T搜索一下答案就好了。那么唯一需要注意的一点就是你在建立边集数组的时候注意变量名的区分（我就是这里爆掉了，我建图的时候是正向和反向一起建立的，但习惯性打Head，以至于反向图的建立爆掉了，而且破坏了正向图的储存）。

  1 //1.路径上的所有点的出边所指向的点都直接或间接与终点连通。
  2 //2.在满足条件1的情况下使路径最短。
  3 //3.图中可能存在重边和自环 
  4 #include<iostream>
  5 #include<cstdio>
  6 #include<cstring>
  7 #include<algorithm>
  8 #include<queue>
  9 #define N 10010
 10 #define M 200010
 11 using namespace std;
 12 
 13 inline long long read(){ 
 14     long long data=0,w=1; 
 15     char ch=0; 
 16     while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar(); 
 17     if(ch=='-') w=-1,ch=getchar(); 
 18     while(ch>='0' && ch<='9') data=data*10+ch-'0',ch=getchar(); 
 19     return data*w;
 20 }
 21 
 22 inline void write(long long x)
 23 {
 24      if(x<0) putchar('-'),x=-x;
 25      if(x>9) write(x/10);
 26      putchar(x%10+'0');
 27 }
 28 
 29 struct Edge{
 30     int startpoint,endpoint,next;
 31 }edge[M],invedge[M];
 32 
 33 int cnt,head[N],invhead[N];
 34 
 35 inline void addedge(int u,int v)
 36 {
 37     edge[++cnt].next = head[u];
 38     edge[cnt].startpoint = u;
 39     edge[cnt].endpoint = v;
 40     head[u] = cnt;
 41     invedge[cnt].next = invhead[v];
 42     invedge[cnt].startpoint = v;
 43     invedge[cnt].endpoint = u;
 44     invhead[v] = cnt;
 45 }
 46 
 47 int n,m,u,v;
 48 int The_start,The_end;
 49 bool visit[N],pass[N],flag_bfs[N];
 50 int ans[N];
 51 
 52 inline void dfs(int u)
 53 {
 54     for(int i=invhead[u];i;i=invedge[i].next)
 55     {
 56         if(!visit[invedge[i].endpoint])
 57         {
 58             visit[invedge[i].endpoint] = true;
 59             dfs(invedge[i].endpoint);
 60         }
 61     }
 62 }
 63 
 64 //int que[N * 10];
 65 
 66 inline void bfs(int u) //这里注释的是我以为我用队列用错了 
 67 {
 68     queue <int> que;
 69     que.push(u);
 70     
 71 //    int head_bfs = 0,tail_bfs = 1;
 72 //    que[tail_bfs] = u;
 73     
 74     flag_bfs[u] = true;
 75     while(!que.empty() /*head_bfs < tail_bfs*/)
 76     {
 77         int aider = que.front() /*que[++head_bfs]*/;
 78         que.pop();
 79         if(aider == The_end) break;
 80         for(int i=head[aider];i;i=edge[i].next)
 81         {
 82             if(pass[edge[i].endpoint] && !flag_bfs[edge[i].endpoint])
 83             {
 84                 que.push(edge[i].endpoint);
 85 //                que[++tail_bfs] = edge[i].endpoint;
 86                 ans[edge[i].endpoint] = ans[aider] + 1;
 87                 flag_bfs[edge[i].endpoint] = true;
 88             }
 89         }
 90     }
 91 }
 92 
 93 int main()
 94 {
 95     freopen("road.in","r",stdin);
 96     freopen("road.out","w",stdout);
 97     
 98     n = read();
 99     m = read();
100     for(int i=1;i<=m;i++)
101     {
102         u = read();
103         v = read();
104         addedge(u,v);
105     }
106     The_start = read();
107     The_end = read();
108     visit[The_end] = true;
109     dfs(The_end);
110     for(int i=1;i<=n;i++)
111     {
112         bool flag = true;
113         for(int j=head[i];j;j=edge[j].next)
114         {
115             if(!visit[edge[j].endpoint])
116             {
117                 flag = false;
118                 break;
119             }
120         }
121         if(flag) pass[i] = true;
122     }
123     bfs(The_start);
124     if(ans[The_end] == 0) write(-1);
125     else write(ans[The_end]);
126         
127     return 0;
128 }