题目大意：
在有向图G 中，每条边的长度均为1 ，现给定起点和终点，请你在图中找一条从起点到终点的路径，该路径满足以下条件：
1 ．路径上的所有点的出边所指向的点都直接或间接与终点连通。
2 ．在满足条件1 的情况下使路径最短。
思路：
先将与终点相通的点求出来（从终点倒着bfs，再将进入未访问到的点的点踢去），再在部分图跑最短路。
代码：
1 #include<cstdio> 2 const int M=200005,INF=10000000; 3 int cnt,n,m,s,t,i,j,o[M],q[M],v[M],w[M],dist[M],last[M],head[M]; 4 bool c[M],g[M],vis[M]; 5 6 void add(int a,int b) { v[++cnt]=b,last[cnt]=head[a],head[a]=cnt,w[cnt]=1; } 7 8 void bfs(int s) 9 { 10 int h=0,t; 11 for (q[t=1]=s,g[s]=1;h<t;) 12 { 13 if (++h>=M) h=h-M; 14 int u=q[h],i; 15 for (i=head[u];i;i=last[i]) 16 if (!g[v[i]]) 17 { 18 g[v[i]]=1; 19 if (++t>=M) t=t-M; 20 q[t]=v[i]; 21 } 22 } 23 } 24 25 int SPFA(int s,int t) 26 { 27 int l=0,r=1,i; 28 for (i=1;i<=n;i++) dist[i]=INF; 29 for (vis[s]=1,q[1]=s,dist[s]=0;l<r;) 30 { 31 if (++l>=M) l=l-M; 32 int u=q[l],i,x; vis[u]=0; 33 if (++o[u]>n) return -1; 34 for (i=head[u];i;i=last[i]) 35 if (!c[v[i]] && dist[x=v[i]]>dist[u]+w[i]) 36 { 37 dist[x]=dist[u]+w[i]; 38 if (!vis[x]) 39 { 40 vis[x]=1; 41 if (++r>=M) r=r-M; 42 q[r]=x; 43 } 44 } 45 } 46 return dist[t]<INF?dist[t]:-1; 47 } 48 49 int main() 50 { 51 scanf("%d%d",&n,&m); 52 for (i=1;i<=m;++i) scanf("%d%d",&s,&t),add(t,s); 53 scanf("%d%d",&s,&t); 54 bfs(t); 55 for (i=1;i<=n;i++) 56 if (!g[i]) 57 for (c[i]=1,j=head[i];j;j=last[j]) c[v[j]]=1; 58 printf("%d\n",SPFA(t,s)); 59 return 0; 60 }
转载于:https://www.cnblogs.com/HHshy/p/6059792.html
