题解 P2296 【寻找道路】

· · 题解

/* problem:road(lg2296,noip20d2t2)

algorithm:搜索剪枝,最短路

这道题硬是做了一个下午, 写的我要死啊...

反向建边应该不要讲了吧,不管是spfa,dfs染色,bfe染色都可以,主要是使出边到的了的情况好判断

接着正着来:

一开始想加个小剪枝,在搜索的时候加最优性剪枝,顺便判断是否符合出边都可以到,如果数据好的话应该可以过70

然并卵,30

于是就不断地加剪枝,删掉重边啊之类的,然后还用了set;

最后忍不住还是看了大神的思路, 原来可以删点啊,于是轻松的删了点后,还是30

再一看,发现正着来不可以深搜,时间复杂度太大了,如果数据中只有一条很小的满足情况的边,剪枝就变得毫无用处

于是果断用bfs或者最短路嘛

我选的最短路,看了边比点多,我就顺手打了个堆优化dijkstra的模板,当然可以过

heap优化的时间复杂度为nlog(n+m),计算器算出来大约2790419

而spfa是km,k一般<=2,所以大约为400000,小了不知道多少...

最后又打了一遍spfa

以下是代码,我将dijkstra的模板和愚蠢的深搜加最优性剪枝都留着了,以此祭奠我宝贵的时间

还有dijkstra的模板要是想套用的话要注意几个点:

1.我用pair之前将pair<>和make_pair都用define代替了

2.我在让他入堆之前依题目需要还有个条件col[v]&&pd[v]==0可以去掉

3.因为题中每条边的长度均为一,固直接加1,其他要加val[i]

4.优先队列的定义为priority_queue<p,vector<p >,greater<p > > q;

5.dijkstra可以重复入堆

另外附赠读入优化的模板>_<

*/

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<queue>
#define maxn 10000+10
#define maxm 200000
#include<set>
#define p pair<int,int>
#define mp(a,b) make_pair(a,b)
using namespace std;
///////////////////////////
int bs,b[maxn],to[maxm],next[maxm];
int BS,B[maxn],TO[maxm],NEXT[maxm];
int n,m,S,T,ans=2100000000;
int dis[maxn];
bool col[maxn],pd[maxn],done[maxn];
queue<int> q;
///////////////////////////
inline int gi()
{
    int ans=0;char temp=getchar();
    while(temp>'9'||temp<'0')
      temp=getchar();
    while(temp<='9'&&temp>='0')
      {
          ans*=10;
          ans+=temp-'0';
          temp=getchar();
      }
    return ans;
}
inline void link(int u,int v)
{
    next[++bs]=b[u];
    b[u]=bs;
    to[bs]=v;
}
inline void knil(int u,int v)
{
    NEXT[++BS]=B[u];
    B[u]=BS;
    TO[BS]=v;
}
/*inline void dijkstra(int s)
{
    memset(dis,0x3f,sizeof(dis));
    q.push(mp(0,s));
    dis[s]=0;
    while(!q.empty())
      {
          p x=q.top();
          q.pop();
          int u=x.second;
          for(int i=b[u];i;i=next[i])
            {
                int v=to[i];
                if(col[v]&&pd[v]==0&&dis[v]>dis[u]+1)
                  {
                      dis[v]=dis[u]+1;
                      q.push(mp(dis[v],v));
              }
          }
      }
    for(int i=1;i<=n;i++)
      cout<<dis[i]<<" ";
    cout<<endl;
}*/
inline void spfa(int s)
{
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;
    done[s]=1;
    q.push(s);
    while(!q.empty())
      {
          int u=q.front();
          q.pop();
          for(int i=b[u];i;i=next[i])
            {
                int v=to[i];
                if(col[v]&&!pd[v]&&!done[v]&&dis[v]>dis[u]+1)
                  {
                      dis[v]=dis[u]+1;
                      q.push(v);
              }
          }
      }
}
inline void in()
{
    //cin>>n>>m;
    n=gi(),m=gi();
    for(int i=1;i<=m;i++)
      {
        int u,v;
        //scanf("%d %d",&u,&v);
        u=gi(),v=gi();
        link(u,v);
        knil(v,u);
      }
    //cin>>S>>T;
    S=gi(),T=gi();
}
int DFS(int x)
{
    col[x]=1;
    for(int i=B[x];i;i=NEXT[i])
      {
          int v=TO[i];
          if(col[v]==0)
            {
                col[v]=1;
                DFS(v);
          }
      }
}
inline void check(int i)
{
    for(int j=B[i];j;j=NEXT[j])
      {
          int v=TO[j];
          pd[v]=1;
      }
}
/*int dfs(int x,int d)
{
    if(d>ans)
      return 0;
    if(x==T)
      ans=min(ans,d);
    for(int i=b[x];i;i=next[i])
      {
          int v=to[i];
          if(pd[v]==0&&col[v]==1)
            {
                pd[v]=1;
                road[++num]=v;
                dfs(v,d+1);
                pd[v]=0;
                road[num--]=0;
          }
      }
}

*/

///////////////////////////
int main()
{
    //freopen("2296(4).in","r",stdin);
    in();
    DFS(T);
    for(int i=1;i<=n;i++)
      if(col[i]==0)
        check(i);
    //dijkstra(S);
    spfa(S);
    if(dis[T]==0x3f3f3f3f)
      cout<<-1;
    else
      cout<<dis[T];
}0.