题解 P2296 【寻找道路】

金闪闪数据球 · 2017-09-21 22:16:10 · 题解

犹记一刷的时候觉得这题贼难，老老实实的建反图删点调了巨久。

现在一看，懒得想那么多，干脆采用最简单的思路吧。

首先明白一点。反图上与终点不连通的点，就是题中所谓的不与终点连通的点（仔细想一想）

所以找这样的点，我们可以建反图广搜。没被访问到的就是

然后，正图的最短路仍然是反图的最短路，因为一组边齐齐转向，s和t的连通性，长度，这两者都不会改变

综上，建一遍反图，一遍广搜删点，再跑一遍最短路

以及。spfa的框架就是广搜，所以删点和最短路可以用同一个函数！！！

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#define N 10010
using namespace std;
struct node{
  int v,nxt;
}e[200010];
int head[N],num;
void add(int u,int v){
  e[num].v=v;
  e[num].nxt=head[u];
  head[u]=num++;
}
int que[N*10],top,dist[N],vis[N];
bool fk[N];
void spfa(int s,int t){
  memset(vis,0,sizeof(vis));
  memset(dist,0x3f,sizeof(dist));
  que[0]=s;
  dist[s]=0;
  top=1;
  for(int i=0;i<top;i++){
    int u=que[i];
    vis[u]=0;
    for(int j=head[u];j!=-1;j=e[j].nxt){
      int v=e[j].v;
      if(fk[v])continue;
      if(dist[v]>dist[u]+1){
    dist[v]=dist[u]+1;
    if(!vis[v]){
      vis[v]=1;
      que[top++]=v;
    }
      }
    }
  }
}
int main(){
  freopen("hh.in","r",stdin);
  freopen("hh.out","w",stdout);
  memset(head,-1,sizeof(head));
  int n,m,a,b,s,t;
  cin>>n>>m;
  while(m--){
    scanf("%d%d",&a,&b);
    add(b,a);
  }
  cin>>s>>t;
  spfa(t,s);
  for(int i=1;i<=n;i++){
    if(dist[i]==dist[0]){
      for(int j=head[i];j!=-1;j=e[j].nxt){
    fk[e[j].v]=1;
      }
    }
  }
  spfa(t,s);
  if(dist[s]==dist[0])cout<<-1;
  else cout<<dist[s];
  return 0; 
}