题解 P2296 【寻找道路】

· · 题解

对一般反向边的做法进行补充。

1.题目的意思是，如果一个点所能到达的点中，有一个点完全无法通过任何路径到达终点，那么这个点不能存在于最短路径上。

于是使用标记数组，三种状态，0为可以到达，-1为完全无法到达，1为不能存在于最短路径上。显然只有值为0的点才可能存在于最短路径上。

2.关于效率问题，刚开始用的是STL结果超时，除了vector全改成手打还是超时，结果发现是忘记判BFS的标记（导致RE与TLE）...因为边权为1，所以直接使用BFS即可，效率更高一点，为O(n)。

3.反向边如何写的问题，结构体两个vector型邻接表，算是空间换时间而且也不算很复杂。

对反向边的做法进行说明：

看代码吧XD

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int N=10010;

int gi(){
    int x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x;
} //读入优化 

struct Graph{
    int glen[N];
    vector<int> to[N];
}G1,G2;//两个邻接表 
void insm(Graph &g,int a,int b){
    g.glen[a]++;
    g.to[a].push_back(b);
}//邻接表通用处理函数 

struct Que{
    int a,len;
}qb[N];
int head,tail,qlen;
inline void insq(Que x){
    qb[tail++]=x;
    tail%=N,qlen++;
}
inline Que delq(){
    Que ret=qb[head++];
    head%=N,qlen--;
    return ret;
}//队列之二 

int tag[N];//标记点，-1为不可至，1为不可走，0为正常 
bool tagb[N];//队列标记 

int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    int a,b;
    for(int i=0;i<m;i++){
        a=gi(),b=gi();
        insm(G1,a,b),insm(G2,b,a);
    }
    int s,t;
    scanf("%d%d",&s,&t);
    memset(tag,-1,sizeof(tag));
    //第一层BFS
    int qu[N];//队列之一，qlen和tail等先用着，之后清零 
    qu[tail++]=t,qlen++,tail%=N;
    tag[t]=0;
    while(qlen){
        a=qu[head++],qlen--,head%=N;
        for(int i=0;i<G2.glen[a];i++){
            if(!tagb[G2.to[a][i]]){
                tagb[G2.to[a][i]]=1;
                tag[G2.to[a][i]]=0;
                qu[tail++]=G2.to[a][i],qlen++,tail%=N;
            }

        }
    }
    //处理类型点1 
    for(int i=1;i<=n;i++){
        if(tag[i]<0){
            for(int j=0;j<G2.glen[i];j++)
                tag[G2.to[i][j]]=1;
        }
    }
    //第二层BFS
    qlen=head=tail=0;
    memset(tagb,0,sizeof(tagb));//队列之二初始化 
    Que c;
    c.a=s,c.len=0;
    insq(c);
    while(qlen){
        c=delq();
        for(int i=0;i<G1.glen[c.a];i++){
            if(!tag[G1.to[c.a][i]]&&!tagb[G1.to[c.a][i]]){
                tagb[G1.to[c.a][i]]=1;
                Que d=c;
                d.a=G1.to[c.a][i];
                d.len++;
                if(d.a==t){
                    cout<<d.len<<endl;
                    return 0;
                }
                insq(d);
            }
        }
    }
    cout<<-1<<endl;
    return 0;
}