[NOIP2014]寻找道路 题解

题目大意：

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

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

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

思路：

　　先将与终点相通的点求出来（从终点倒着bfs，再将进入未访问到的点的点踢去），再在部分图跑最短路。

代码：

 #include<cstdio>

 const int M=,INF=;

 int cnt,n,m,s,t,i,j,o[M],q[M],v[M],w[M],dist[M],last[M],head[M];

 bool c[M],g[M],vis[M];

 void add(int a,int b) { v[++cnt]=b,last[cnt]=head[a],head[a]=cnt,w[cnt]=; }

 void bfs(int s)

 {

     int h=,t;

     for (q[t=]=s,g[s]=;h<t;)

     {

         if (++h>=M) h=h-M;

         int u=q[h],i;

         for (i=head[u];i;i=last[i])

             if (!g[v[i]])

             {

                 g[v[i]]=;

                 if (++t>=M) t=t-M;

                 q[t]=v[i];

             }

     }

 }

 int SPFA(int s,int t)

 {

     int l=,r=,i;

     for (i=;i<=n;i++) dist[i]=INF;

     for (vis[s]=,q[]=s,dist[s]=;l<r;)

     {

         if (++l>=M) l=l-M;

         int u=q[l],i,x; vis[u]=;

         if (++o[u]>n) return -;

         for (i=head[u];i;i=last[i])

             if (!c[v[i]] && dist[x=v[i]]>dist[u]+w[i])

             {

                 dist[x]=dist[u]+w[i];

                 if (!vis[x])

                 {

                     vis[x]=;

                     if (++r>=M) r=r-M;

                     q[r]=x;

                 }

             }

     }

     return dist[t]<INF?dist[t]:-;

 }

 int main()

 {

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

     for (i=;i<=m;++i) scanf("%d%d",&s,&t),add(t,s);

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

     bfs(t);

     for (i=;i<=n;i++)

         if (!g[i])

             for (c[i]=,j=head[i];j;j=last[j]) c[v[j]]=;

     printf("%d\n",SPFA(t,s));

     return ;

 }