【NOIP2014T】寻找道路

· · 题解

此题的数据量并不是很大，宽搜也是可以过得。

如何除去第一个条件，这题还是比较裸的，但是加上第一条件就不一样了。

但是经过思考我们还是可以发现，如果我们可以预先将其中到不了终点的点直接去掉，保留其他点，这不就变成了一个裸题了吗。

我们开始思考如何预处理。

如果我们顺向去找，不尽程序变得复杂，而且同时还会增加复杂度。

既然这样那么要找到t的，我们为何不从t开始向前找，只要从t可以扩展的点，一定可以从它载扩展到t。

这样我们就可以简简单单几行小程序，就可以实现预处理。

最后加上bfs或最短路即可。

【time complexity】

O(n)

【accepted code】

#include<bits/stdc++.h>

using namespace std;

int n,m;

vector<int>a[11111],ab[11111];

struct node {

  int po,step;

  node(int _po,int _step):po(_po),step(_step){}

};

queue<node>dl;

int s,t;

int vhash[11111],vh[11111];

void dfs(int k){

    vhash[k]=1;

     for(int i=0;i<ab[k].size();i++)

    if(vhash[ab[k][i]]==0)

   dfs(ab[k][i]);

}

int main(){

   freopen("road.in","r",stdin);

   freopen("road.out","w",stdout);

   cin>>n>>m;

   for(int i=1;i<=m;i++)

   {

      int x,y;

      cin>>x>>y;

      a[x].push_back(y);

      ab[y].push_back(x);

   }

   cin>>s>>t;

   dfs(t);

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

   {

      bool flag;

      if (vhash[i]) flag=true;else flag=false;

      for(int j=0;j<a[i].size();j++)

        if(vhash[a[i][j]]==0) flag=false;

      if(flag){vh[i]=1;//cout<<i<<endl;*/}

   }

}

   dl.push(node(s,0));

   while(!dl.empty()){

      int qt=dl.front().po;

      int f=dl.front().step;

       for(int i=0;i<a[qt].size();i++){

           if(vh[a[qt][i]]==1){

              vh[a[qt][i]]=0;

            dl.push(node(a[qt][i],f+1));

      if(a[qt][i]==t){

          cout<<f+1<<endl;

          return 0;

      }

         }

      }

      dl.pop();

   }

   cout<<"-1"<<endl;

   return 0;

}